В 1506 году он поступил на службу к Габсбургам. Герберштейн участвовал в походе против Венгрии, предпринятом Максимилианом, тогда еще носившим титул римского короля, ради заключения брака одного из его внуков – Фердинанда с Анной, дочерью венгерского короля Владислава Ягеллона.

Во время войны с Венгрией за успешную доставку провианта в осажденную крепость Маран и разгром вражеского отряда в ходе очередной вылазки против венецианцев Герберштейн удостоился посвящения в рыцари самим Максимилианом, разглядевшим в юном выходце из Штирии не только отважного воина, но и разумного и осторожного политика (1508). Рыцарь по воле римского короля превратился в дипломата.

С 1515 года Герберштейн стал членом Имперского совета, а в 1516 году он получил деликатное поручение – убедить датского короля Кристиана II в необходимости хранить верность собственной супруге Изабелле – внучке Максимилиана I и сестре будущего императора, а пока герцога бургундского Карла – и расторгнуть связь с дочерью трактирщицы Сигбрид, некоей Дивеке. Король уже тогда был известен жестокостью и неуравновешенностью. Герберштейну удалось добиться аудиенции у короля, но на этом успехи дипломата закончились. Получив отрицательный ответ, Герберштейн тем не менее завоевал благосклонность Кристиана II.

Неудача миссии не повлияла на дальнейшую карьеру Герберштейна. Неукоснительное следование инструкциям, твердость, разумная настойчивость и корректность, проявленные послом в Дании, произвели впечатление при дворе. Через несколько месяцев в Вене Герберштейн получил полномочия посла императора в Московию.

Не останавливаясь подробно на сложном международном положении 20-х годов XVI века, отметим, что поездка Герберштейна была одним из ходов запутанной игры Габсбургов, пытавшихся одновременно предотвратить наметившееся сближение Москвы с Данией, Ливонским орденом и Францией, а также создать заслон на северо-востоке против турецких полчищ, вторгшихся на Балканы и угрожавших дунайской империи. Задачи эти оказались чрезвычайно сложными и практически невыполнимыми.

В конце 1516 года из Вены в Вильно и Москву отправилось посольство барона Сигизмунда Герберштейна. Первую часть своей сложной миссии оно выполнило успешно. Герберштейн представил польскому королю его невесту принцессу Бону, которая совершенно очаровала его. Сигизмунд изложил имперскому послу свою программу мирного урегулирования отношений с Россией. Непременным условием было возвращение Великому княжеству Смоленска. Теперь оставалось склонить к принятию этого условия Василия III, и Герберштейн мог бы считать свою поездку блистательным триумфом. 18 апреля он прибыл в Москву. И здесь имперскому послу была устроена торжественная встреча. 22 апреля начались переговоры. К их главной теме (заключение мира с Литвой и союза против турок) Герберштейн подходил исподволь. Свою речь он начал с того, что весьма красочно описал ту угрозу, которую представляли для христианского мира турки. Единственное спасение от грозящей беды – это соединение и согласие между христианскими державами.

Герберштейн старался внушить Василию III мысль, что война с Турцией – главная задача, которая должна волновать русское правительство. Но, вероятно, он, как, впрочем, и Максимилиан, не сознавал, что идея втянуть Россию в войну с Турцией (которая для Москвы представлялась потенциальным союзником, а не врагом) была утопичной.

Страшные картины «турецкой опасности», нарисованные Герберштейном, оказали воздействие на московский двор совершенно противоположное тому, на которое рассчитывал опытный имперский дипломат. Великий князь Василий III и его окружение еще раз убедились в необходимости сохранять дружеские отношения с Портой.

Русские дипломаты оставили у имперского посла полную иллюзию согласия России на «единачество» с другими «христианскими державами» для борьбы с «врагами христианства». Это было совершенно необходимо для того, чтобы добиться своей цели – использовать имперское посредничество при заключении выгодного и прочного мира с Великим княжеством Литовским.

Дело оказалось сложным. Василий III хотел, чтобы мирные переговоры велись в Москве, а именно этого и не желал Сигизмунд. Для уточнения места ведения переговоров русское правительство разрешило племяннику Герберштейна Гансу фон Турну 26 апреля отбыть ко двору польского короля. Вернувшись 14 июля в Москву, он сообщил, что король Сигизмунд согласен прислать своих послов только на русско-литовскую границу. Василия III это не устраивало. Переговоры, таким образом, зашли в тупик еще прежде, чем начались. Камнем преткновения стал «процедурный» вопрос. Ганс фон Турн снова был послан в Литву. Он передал королю, что Герберштейн будет считать свою посредническую миссию законченной, если тот согласится, чтобы переговоры происходили в Москве. Под нажимом имперского дипломата Сигизмунд принял это условие.

Литовские послы Ян Щит и Богуш прибыли в Москву 3 октября 1517 года. Посредником в переговорах выступал Герберштейн. Московский государь торжественно заявил, что готов примириться с Сигизмундом ради своего «брата» Максимилиана и из-за того, чтобы «рука бесерменская не высилася и государи бы бесерменские вперед не ширились, а христианских бы государей над бесерменством рука высилася и государства бы христианские ширились». Эта расплывчатая формулировка о «бесерменских государях» вообще давала русским дипломатам возможность интерпретировать ее так, как им выгодно, и одновременно создавала впечатление готовности России вступить в антитурецкую лигу.

Гораздо труднее приходилось обеим сторонам, когда нужно было от деклараций переходить к рассмотрению конкретных условий мира. Василий III заявил, что Сигизмунд «неправдою» держит «отчину» русских князей – Киев, Полоцк и Витебск. Справедливость русских требований фактически была признана по договору 1514 года России с империей, и, когда русские дипломаты сослались на этот договор, Герберштейну ничего не оставалось, как заявить, что договор заключен «не по государя нашего велению».

Со своей стороны литовские послы говорили о том, что им издревле принадлежит не только Смоленск, но и Новгород, Псков, Вязьма и Северщина. Разговор, словом, велся на столь различных языках, что о взаимопонимании не могло быть и речи. Прояснила, но не облегчила ситуацию позиция, занятая Герберштейном. Он высказался за передачу Смоленска Литве, сославшись на пример Максимилиана, отдавшего Верону ее гражданам. Но отказываться от старинного русского города, присоединенного с таким большим трудом, Москва не собиралась.

Не возражая в принципе против продолжения переговоров, московские дипломаты решительно отклонили предложения Герберштейна. Ему ничего не оставалось, как покинуть Москву. 22 ноября он вместе с московским послом дьяком В.С. Племянниковым отбыл к имперскому двору.

Итог первой миссии Герберштейна в Москву не принес желаемого результата. Тем не менее отношения Московии с империей, прерванные после Венского конгресса, были возобновлены.

Осенью того же года австрийский посол возвратился в Вену. Видимо, здесь, в столице империи, в кружке венских гуманистов, внимавших его рассказам о далекой и необычной Московии, у Герберштейна впервые возникла мысль написать книгу о своем путешествии. Немаловажную роль могли сыграть и дневники, которые вел Герберштейн во время путешествия. Но прошло еще много лет, прежде чем эта идея осуществилась.