The era of artificial intelligence (AI) and big data presents significant opportunities for implementing federated health data networks across national borders. However, these opportunities are accompanied by substantial challenges. This study documents barriers and facilitators identified during the early phases of establishing the Nordic-Baltic Federated Health Data Network, prior to technical implementation. Utilizing a mixed-methods approach, we identified and prioritized key factors affecting consortium formation. Our findings reveal five key facilitator clusters that drive the project forward, including strong motivation, interdisciplinary collaboration, and regulatory alignment. Additionally, we identified six major barrier clusters, with security and privacy concerns and technical infrastructure challenges emerging as the most critical. These barriers impact both human collaboration and technical aspects, emphasizing the dual nature of network development. By providing a prioritized list of barriers and actionable strategies for addressing them, this study offers pre-implementation guidance for future consortia. These strategic insights can help teams better prepare for establishing cross-border federated health data networks.