Первые сведения о службе Андрея Васильевича относятся к 1591 г. Он получил должность стольника и должен был обслуживать наиболее знатных бояр, сидящих за большим столом. Назначение дает право предположить, что в это время ему было лет 16. Именно в этом возрасте в то время начинали службу при дворе юноши из княжеских и боярских семей. Однако исполнять эту должность Андрею не пришлось, поскольку его старший брат Василий, назначенный стольником при кривом столе, где сидели менее важные лица, потребовал устроить местнический суд. В ходе него было выяснено, что Василий старше Андрея и поэтому имел больше прав на более высокую должность.
Ошибка при данном назначении появилась, видимо, из-за того, что Андрей был выше брата ростом и имел более привлекательную внешность. Об этом свидетельствует его прозвище Скуриха – высокий и стройный.
Первое военное назначение A.B. Голицын получил только в 1598 г. в возрасте приблизительно 23 лет. Во время Серпуховского похода выборного царя Б.Ф. Годунова против крымских татар он вместе с братьями был зачислен в Государев полк в должности есаула. В его обязанности входило выполнять личные поручения царя: отвозить его грамоты в полки или в Москву раздавать награды воинам и т. д.
Первые назначения A.B. Голицына свидетельствовали о том, что он находился в ближнем царском окружении. Однако в 1603 г. он вдруг оказался на воеводстве в Тобольске вместе с дворянами Н.М. Пушкиным, Г.В. Хлоповым и П.А. Вельским. Поскольку в то время служба в Сибири считалась ссылкой, напрашивается вывод о том, что либо сам князь, либо кто-либо из его родственников провинились перед царем Борисом. Но по источникам никаких сведений о проступках A.B. Голицына нет. К тому же никто из его братьев в это время не пострадал. Значит, дело было не в них. Причиной ссылки могло быть родство жены Андрея Васильевича Марии Васильевны Морозовой с женой опального Ф.Н. Романова Ксенией Ивановной Шестовой-Морозовой, которая в 1601 г. из-за явно надуманных обвинений в адрес братьев Романовых была пострижена в монахини и отправлена в Заонежье. (Романовых обвинили в том, что с помощью ядовитых корешков они хотели отравить царя Бориса Годунова.) Возможно, Мария Васильевна сочувствовала своей невинно осужденной родственнице и даже поддерживала с ней связь, о которой стало известно царю Борису. Поэтому наказание в адрес Андрея Васильевича последовало не сразу, а спустя два года после осуждения Романовых.
В ссылке в Сибири A.B. Голицын, видимо, находился до конца правления Годуновых. Вызволил его оттуда самозванец Лжедмитрий I, считавший себя покровителем всех опальных лиц и родственников царя Федора Ивановича (Романовы были его двоюродными братьями). Князь не только оказался при царском дворе, но и получил боярский чин вместе со средним братом Иваном. Старший Василий к тому времени уже давно был боярином. Однако в Совете светских лиц (так стала называться Боярская дума) положение Голицыных ухудшилось. Они заняли места ниже достаточно худородных Нагих, мнимых родственников Лжедмитрия, и его новых любимцев Мосальских.
Умаление родовой чести, видимо, настолько повлияло на братьев Голицыных, что они примкнули ко второму заговору князя В.И. Шуйского, закончившемуся 14 мая 1606 г. свержением и убийством Лжедмитрия I. После этого они заняли одно из ведущих мест при дворе нового царя Василия.
Однако уже летом 1606 г. выяснилось, что в Путивле собирается новое войско якобы спасшегося «царя Дмитрия». Во главе него был назначен беглый холоп И.И. Болотников. Царь Василий отправил против него полки, но под Кромами они были разбиты и отступили к Москве. Путь к столице оказался для восставших болотниковцев свободным, и они вскоре взяли город в блокадное кольцо.
В это время A.B. Голицын под началом М.В. Скопина-Шуйского стоял за Москвой-рекой у Данилова монастыря и мужественно отбивал все атаки повстанцев. Только к декабрю 1606 г. царю В.И. Шуйскому удалось сформировать боеспособные полки из стольников, стряпчих и московских дворян, которым предстояло дать бой И. Болотникову. Его возглавили князья М.В. Скопин-Шуйский и A.B. Голицын. Так состоялось близкое знакомство князя Андрея с талантливым и смелым полководцем, которому в будущем предстояло стать спасителем Отечества от Тушинского вора и его сторонников.
Ожесточенный бой состоялся 2 декабря под Коломенским. Скопину вместе с Голицыным удалось наголову разбить И.И. Болотникова и заставить его отойти к Калуге. Это знаменательное сражение, видимо, многому научило Андрея Васильевича, поскольку до этого он не имел воинского опыта, как его старшие братья. К тому же у него был превосходный учитель – самый талантливый полководец того времени М.В. Скопин-Шуйский.