Стекеленбург играе в Аякс от 2001 година. На 24 февруари 2002 дебютира за първия тим в мач срещу НАК Бреда. До 2005 година Маартен е втори вратар, като изиграва 30 мача. През годините пред него са предпочитани Богдан Лобонт, Хенк Тимер, Джо Дидулица и Ханс Вонк. През сезон 2005/06 измества Вонк от титулярното място и прави добър сезон. Получава повиквателна в националния отбор на Холандия за Мондиал 2006, но е резерва на Едвин ван дер Саар. През сезон 2008/09 треньорът Марко ван Бастен оставя Стекеленбург резерва за сметка на Кенет Вермеер в продължение на няколко мача. Скоро след това, Стекеленбург си връща титулярното място, като също така става и титуляр на вратата на Холандия. Играе във всичките 7 мача на Мондиал 2010.
На 31 юли 2011 преминава в Рома. А на 5 юни 2013 година преминава в английския Фулъм. За сумата от 5,5 милиона паунда където отива при треньора, който го водеше в Аякс Амстердам, Мартин Йол. Маартен Стекеленбург заиграва с номер 1 и подписва договор до 30 юни 2017 година. След като Фулъм изпада от Висшата лига, Стекеленбург преминава под наем в Монако, но там е резерва на Даниел Субашич.