L'idée que les parlementaires s'investissent dans les problèmes transatlantiques remonte au début des années 1950 et prend forme, en 1955, avec la création d'une conférence annuelle des parlementaires de l'OTAN. La constitution d'un tel ensemble s'explique par le souhait des législateurs de donner corps au préambule du traité de Washington, qui dispose que l'OTAN est l'expression concrète d'une alliance transatlantique et foncièrement politique de nations démocratiques.
Le fondement de la coopération entre l'OTAN et l'AP-OTAN est renforcé en décembre 1967, lorsque le Conseil de l'Atlantique Nord invite le secrétaire général de l'OTAN à étudier les solutions permettant d’intensifier la coopération entre les deux institutions. À l'issue des délibérations, le secrétaire général de l'OTAN, après consultation du Conseil, applique plusieurs mesures destinées à améliorer les relations de travail entre l'OTAN et l'Assemblée. Il est ainsi décidé que le secrétaire général donnera suite à toutes les recommandations et résolutions de l'Assemblée adoptées pendant les sessions plénières.
Promouvoir la démocratie parlementaire en Europe centrale et orientale
Après la chute du mur de Berlin dans les années 1980, l'AP-OTAN élargit la portée de son mandat et développe des relations étroites avec les responsables politiques de pays de l'Europe centrale et orientale. Les liens ainsi tissés facilitent grandement le dialogue que l'OTAN amorce avec les gouvernements de la région.
Le programme Rose-Roth de coopération avec les parlements de pays d'Europe centrale et orientale (PECO) est lancé en 1990 par deux membres du Congrès américain : Charlie Rose, membre de la Chambre et, à l'époque, président de l'Assemblée, et Bill Roth, sénateur. L'initiative Rose-Roth vise, dans un premier temps, à renforcer le développement de la démocratie parlementaire dans les PECO.
Approfondir les relations avec la Russie et l'Ukraine
À la fin de la Guerre froide, l'AP-OTAN noue des contacts avec la Russie et l'Ukraine. En 1997, les relations avec ces deux pays prennent un nouvel essor avec, en mai, la signature de l'Acte fondateur sur les relations, la coopération et la sécurité mutuelles entre l'Organisation du Traité de l'Atlantique Nord et la Fédération de Russie, suivie, en juillet, par la Charte OTAN-Ukraine. Aux termes de ces accords, l'Assemblée doit intensifier son dialogue et sa coopération avec l'Assemblée fédérale de Russie et la Rada ukrainienne.
À l'instar de l'OTAN qui crée, en mai 2002, le Conseil OTAN-Russie (COR), étape décisive dans la coopération de l'OTAN avec la Russie, l'Assemblée institue la Commission parlementaire OTAN-Russie permettant ainsi des débats à 27. La commission, qui se réunit deux fois par an pendant les sessions, est devenue le cadre formel des relations parlementaires directes entre l'OTAN et la Russie.
En 2002, l'Assemblée décide également de revaloriser la relation spéciale qu'elle entretient avec l'Ukraine en constituant le Conseil interparlementaire Ukraine-OTAN. En 2004, l'Assemblée renforce progressivement sa coopération avec la Verkhovna Rada en participant à la mission internationale d'observation des élections présidentielles jusqu'aux résultats du scrutin.
Renforcer la coopération avec les partenaires au Moyen-Orient et en Afrique du Nord
L'attention croissante portée à la sécurité de la région méditerranéenne dans les années 1990 débouche, en 1996, sur la création du Groupe spécial Méditerranée de l'Assemblée, enceinte de coopération et de discussion avec les parlements des pays du Moyen-Orient et d’Afrique du Nord (MOAN) pour les questions de politique, d'économie, de société et de sécurité.
En 2004-2005, l'Assemblée décide de renforcer ses relations avec les parlements de cette région et, à la session de Venise, la Commission permanente instaure le nouveau statut de membre associé méditerranéen, ouvrant ainsi la voie à une coopération accrue avec les parlements du MOAN.
