Ponieważ nie mógł się porozumieć z odgrywającym coraz większą rolę następcą tronu Janem II, w 1480 wyjechał z Portugalii do Rzymu i przeszedł na służbę papieską. Sykstus IV i Innocenty VIII powierzali mu szereg misji dyplomatycznych (np. w 1484 był legatem a latere na negocjacje pokojowe państw włoskich w Wenecji). W styczniu 1486 został wybrany kamerlingiem Świętego Kolegium Kardynałów i sprawował tę funkcję co najmniej przez jedną kadencjęKamerlingowie Świętego Kolegium byli wybierani na roczną kadencję, jednak pierwszym znanym następcą da Costy jest dopiero Lorenzo Cibo w 1492. Nie wiadomo, kto sprawował tę funkcję w latach 1487–1491, zob. Eubel, II, s. 59.. W 1491 awansował do rangi kardynała biskupa, otrzymując kolejno diecezje podmiejskie: Albano, Tusculum i Porto e Santa Rufina. W maju 1492 eskortował relikwię Świętej Włóczni z Narni do Rzymu. Na konklawe 1492 był wysuwany jako kandydat na papieża, jednak tiarę uzyskał wówczas Rodrigo Borgia. W latach 1495–1496 był komendatariuszem archidiecezji Genui, a w 1501–1505 administratorem archidiecezji Bragi. W 1497 należał do komisji kardynalskiej mającej przygotować projekt reformy Kościoła (nigdy nie wdrożono go w życie). Po wyborze papieża Juliusza II został jego następcą na stanowisku protektora zakonu franciszkanów, był też jego bliskim współpracownikiem i doradcą.