Škrtel pochodzi z małej miejscowości Handlová leżącej niedaleko Prievidzy. Piłkarską karierę zaczynał jednak gdzie indziej, bo w Trenczynie w klubie Laugaricio Trenčín i z młodzieżową drużyną wywalczył w 2001 roku mistrzostwo Słowacji. W Corgoň Liga zadebiutował w wieku 19 lat w barwach tego klubu w sezonie 2002/2003 zaliczając w nim jeden symboliczny występ. W sezonie 2003/2004 był już jednak podstawowym zawodnikiem swojego zespołu i w sezonie rozegrał 34 mecze będąc pewnym punktem Laugaricio w obronie. Z klubem z Trenczyna zajął 5. pozycję w lidze.

Latem 2004 Škrteľ za darmo przeszedł do klubu z Rosyjskiej Premier Ligi Zenitu Sankt Petersburg. W barwach Zenitu Martin zadebiutował 31 lipca w wygranym 2:0 wyjazdowym meczu Pucharu Rosji z Irtyszem Omsk. Do końca roku zagrał w 7 ligowych meczach i z Zenitem zajął 4. miejsce w lidze. W 2005 roku grał więcej, ale nie zawsze był pewny miejsca w podstawowym składzie. Rozegrał 18 ligowych meczów i zdobył swoją pierwszą bramkę nie tylko w rosyjskiej lidze, ale w ogóle na pierwszoligowych boiskach. Fakt ten miał miejsce 21 sierpnia w zremisowanym wyjazdowym meczu z CSKA Moskwa. Ze swoim klubem zajął 6. pozycję w lidze. W roku 2006 był już podstawowym graczem swojej drużyny i przez cały sezon zaprezentował wysoką równą formę co znalazło odzwierciedlenie w plebiscycie na Najlepszego Piłkarza Słowacji, w którym zajął 2. miejsce. W lidze rosyjskiej zagrał w 26 meczach i strzelił 1 gola (w wygranym 2:1 wyjazdowym meczu z Szynnikiem). Z Zenitem zajął 4. miejsce w lidze. W 2007 roku osiągnął największy, jak do tej pory, sukces w karierze - zdobył z Zenitem mistrzostwo Rosji.

Na początku 2008 roku Škrteľ przeszedł do Liverpool F.C.. Kosztował 6,5 miliona funtów. W Premiership Słowak zadebiutował 5 marca 2008 w wygranym 4:0 domowym spotkaniu z West Ham United.