Начал заниматься футболом с 6 лет. Воспитанник футбольной школы клуба Прьевидза, в котором играл на позициях защитника и опорного полузащитника. Позднее играл за Тренчин, откуда в 2004 году перебрался в петербургский Зенит. Дебютировал в Зените словак в июле 2004 года в матче на Кубок России против омского Иртыша и провёл в клубе 4 сезона. В составе Зенита в 2007 году стал чемпионом России. По итогам того же года Шкртел был назван Футболистом года в Словакии.

11 января 2008 года он перешёл в Ливерпуль. Во время переговоров Ливерпуля и Зенита на Мартина произвел сильное впечатление главный тренер Ливерпуля Рафаэль Бенитес, что впоследствие футболист назовет решающей причиной выбора именно этого клуба. Предполагаемая сумма трансфера составила 6,5 миллионов фунтов. Рафаэль Бенитес на пресс-конференции, посвящённой подписанию Шкртела его главными качествами назвал "настойчивость, скорость и хорошую игру в воздухе" и сравнил Мартина с вице-капитаном "Красных", легендарным защитником Джейми Каррагером..

В новой команде Шкртел получил номер 37, который до него носили Яри Литманен и Зак Уитбред. Его полноценный дебют состоялся 26 января 2008 года в матче против любительского клуба Хавант-энд-Уотерлувилл в рамках четвертого раунда Кубка Англии. Мартин практически сразу завоевал место в основном составе, за первые три месяца в команде сыграв, в частности, в важнейших играх против Челси, Манчестер Юнайтед, Эвертона и Арсенала. По итогам своего первого мерсисайдского дерби Шкртел был признан болельщиками Ливерпуля лучшим игроком матча.

В начале сезона 2008-09 в матче против Манчестер Сити Шкртел получил тяжелейшую травму крестообразных связок. Тем не менее, он успел восстановиться к Новому году и набрать оптимальную форму.

Серьезная травма - перелом плюсневой кости - и долгое восстановление не позволили Мартину принять участие более, чем в 29 из 56 матчей Ливерпуля в сезоне 2009-10. Но он все же поехал на Чемпионат мира, где со сборной Словакии дошел до 1/8 финала.

Следующий сезон стал для словака по истине выдающимся. На ряду с Лейтоном Бэйнсом из Эвертона он стал единственным полевым игроком, не пропустившим ни одной минуты матча Премьер-лиги, по ходу которой в Ливерпуль вернулся Кенни Далглиш.

В сезоне 2011-12 Шкртел столкнулся с серьезной конкуренцией в лице Даниэля Аггера, который восстановился от очередной травмы и наверняка столкнется с борьбой с Себастьяном Коатесом, перешедшим в Ливерпуль летом.