Происхождением из малоизвестного и маловлиятельного рода. Отец его Яков Семенович Щелкалов был дьяком. Андрей был старше своего брата Василия на десять лет.
Несмотря на свое низкое происхождение, он вместе с Василием достиг большого влияния на государственные дела в последней четверти XVI века. В течение своей почти полувековой службы Щелканов исполнял разнообразнейшие поручения, занимал различные должности и места и управлял иногда несколькими приказами одновременно.
Впервые имя Андрея Щелкалова появляется в 1550 году, когда он был записан в «тысячную книгу» и состоял «в разрядах в числе поддатней у рынд». В этой должности он упоминается также в 1556 году в походных списках.
В 1560 году он был приставом при литовских послах, а через три года и дьяком. Впоследствии стоял во главе Разрядной избы и Посольского приказа.
В 1564 году он в числе нескольких доверенных людей Ивана Грозного упоминается при встрече последнего с литовским послом Михаилом Гарабурдой. Эта встреча происходила в Новгороде.
В 1566 году Щелкалов участвовал на земском соборе, подписал его определение и скрепил поручную грамоту по князе Михаиле Ивановиче Воротынском.
В 1581 году он вел все переговоры с иезуитом Антоном Поссевином, а в 1583 году — с английским послом Еремеем Баусом, который в письме от 12 августа 1584 года написал следующее: «объявляю, что когда я выехал из Москвы, Никита Романов и Андрей Щелкалов считали себя царями и потому так и назывались многими людьми».
Иностранцы, особенно англичане, не любили Андрея Щелкалова, равно как и его брата Василия Яковлевича, и давали о них весьма нелестные отзывы, главным образом из-за того, что Щелкаловы стремились к уничтожению торговых привилегий иностранных купцов.
Борис Годунов, считая его необходимым для управления государством, был очень расположен к этому дьяку, стоявшему во главе всех прочих дьяков в целой стране. Во всех областях и городах ничего не делалось без его ведома и желания. Борис Годунов высоко ценил Щелкалова за его ум, ловкость дипломатическую, но позже подвергнул его опале за «самовольство»: Андрей Яковлевич и его брат Василий «искажали росписи родословных людей и влияли на местнический распорядок, составляя списки административных назначений». Вообще, они достигли такого влияния, какого дьяки не имели никогда.
Умер Андрей Яковлевич Щелкалов, приняв иночество с именем Феодосия.