В любительском боксе Кречманн последовательно преодолел все ступени, которые приходится преодолевать юному спортсмену, перешагивающему порог боксерской школы с мечтой попасть со временем в национальную сборную своей страны. Штеффен оказался способным учеником и его первые серьёзные успехи на внутренней, а затем и международной арене не заставили себя долго ждать. В 1996 году молодой немец, выступавший тогда в полутяжелой весовой категории, выиграл чемпионат Европы среди кадетов (до 17 лет), а годом позже, поднявшись в следующую возрастную группу, занял второе место на молодежном европейском первенстве, проходившем в английском Бирмингеме. В 1998-м окрепший, потяжелевший и перешедший в связи с этим в тяжелую весовую категорию Кречманн дебютировал на турнирах планетарного масштаба, приняв участие в молодежном чемпионате мира в Аргентине. По ходу состязаний Штеффену удалось одержать победу над будущим олимпийским чемпионом Пекина-2008 итальянцем Роберто Камарелле, однако в четвертьфинале Кречманн безоговорочно уступил боксеру, также ставшему впоследствии триумфатором Олимпийских игр — кубинцу Одланьеру Солису.
Переход во взрослые соревнования дался немецкому боксеру абсолютно безболезненно. 1999 год вообще стал одним из самых ярких в его карьере — Кречманн выиграл национальное первенство и отлично выступил на чемпионате мира, проходившем в американском Хьюстоне. Там, в Штатах, он дошёл до стадии полуфиналов, где встретился в бою за право участвовать в финале турнира с хозяином ринга Майклом Беннетом. Во втором раунде поединка, пробивая апперкот, Штеффен вывихнул руку и не смог продолжить схватку, что автоматически сделало его бронзовым призёром чемпионата. В то время Кречманн по праву считался главным претендентом на участие в приближающейся Олимпиаде-2000, но заполучить олимпийскую лицензию ему было не суждено. На национальном уровне в тяжелой весовой категории у Штеффена появился достойный конкурент, Себастьян Кёбер, острое соперничество с которым в начале 2000-х приносило уроженцу Кётена сплошные неприятности. Несмотря на победы Кречманна в чемпионатах Германии в 2001-2002 годах, Кёбер всякий раз наглядно убеждал тренеров сборной в том, что на крупные международные турниры следует везти именно его. В 2003-м злой гений Штеффена принял решение перейти в супертяжелую весовую категорию. Кречманн воспользовался этим сполна, пробившись на чемпионат мира-2003, проходивший в столице Таиланда Бангкоке. Немецкий боксер отметил возвращение в основной состав сборной своей второй в карьере «бронзой», уступив лишь в полуфинале сильному россиянину Александру Алексееву. Начиная с 2004 года Штеффен выступал в супертяжелой весовой категории и в новом статусе супертяжа завоевал серебряную медаль на чемпионате мира среди военнослужащих (2004 год). Однако пробиться на Олимпиаду-2004 Кречманну вновь не удалось, причем по банальной причине — после «подъема» в более тяжелую весовую категорию на его пути в очередной раз встал пресловутый соотечественник Кёбер. Аналогичным образом не попав в 2005 году на чемпионат Европы, Штеффен принял решение попробовать себя в профессиональном боксе. Всего за время выступлений в любительских соревнованиях Кречманн провёл 144 боя, одержав в них 122 победы.
На профессиональном ринге Кречманн дебютировал 10 ноября 2006 года в возрасте 26 лет, все свои бои провёл в Германии и Турции под эгидой известной немецкой промоутерской компании «Арена Бокс-Промоушн». Хорошо оснащен технически, координирован, обладает сильным ударом слева, но при этом не отличается высокой скоростью передвижения по рингу, и по состоянию на 31 октября 2008 года ни разу не встречался с соперником, способным провести качественную проверку его защитных навыков.
Данный период Кречманн провёл чрезвычайно активно. Так, после дебюта в ноябре 2006-го, Штеффен до конца года провёл ещё два боя (правда, с соперниками откровенно низкого уровня), завершив все эти поединки зрелищными нокаутами.
В 2007 году Кречманн выходил на ринг семь раз, причём у пятерых его оппонентов количество побед в послужных списках превосходило количество поражений. Но это никак не сказался на успешных выступлениях Штеффена — выходцы с территории бывшего СССР Игорь Шукало, Эдгар Калнарс и Толгат Досанов не продержались и двух раундов, а серб Ивица Перкович не смог продолжать поединок после третьего. Даже такой опытный боксёр, как американец Кори Сандерс, побеждавший в свое время Олега Маскаева и встречавшийся на ринге с Майклом Грантом, Анджеем Голотой и Дэвэррилом Уильямсоном, хоть и прошёл всю дистанцию восьмираундового боя, доставить при этом особых проблем Кречманну не сумел.
В марте 2008 года Штеффен завоевал свой первый в профессиональной карьере чемпионский пояс. Воспользовавшись представившейся возможностью побороться за вакантный титул интернационального чемпиона Германии, добровольно оставленный перспективным белорусским тяжеловесом Александром Устиновым, Кречманн явно не прогадал.
Соперником немца стал достаточно опытный латвийский боец Алексей Кособоков, имевший за плечами солидную практику любительских и профессиональных поединков. Кречманн уверенно переигрывал соперника и на дистанции, и в ближнем бою — подчас происходившее в ринге напоминало одностороннее избиение. В седьмом раунде рефери Арно Покрандт счёл, что пропущенное Кособоковым количество ударов перевалило за некую критическую отметку и зафиксировал победу Штеффена техническим нокаутом.
После победы в титульном бою Кречманн не появлялся на ринге в течение полугода, приняв решение отказаться от завоеванного пояса. Вернувшись, Штеффен уверенно разобрался с не представлявшими для него никакой опасности американским тяжеловесом Отисом Тисдейлом и соотечественником Марселем Целлером. После победы над Целлером Кречманн заявил, что хотел бы в будущем претендовать на титул чемпиона Европы (EBU).