Cuộc họp kín đầu tiên diễn ra vào tháng 6/2013 tại Ottawa, sau khi chính phủ Canada đồng ý cung cấp một địa kín đáo, bỏ qua một số thủ tục về nhập cảnh và hải quan, cũng như chu cấp phương tiện đi lại phù hợp cho hai đoàn đàm phán. 

Nhóm đàm phán của Cuba cũng nhỏ gọn, gồm những người gần gũi nhất với Chủ tịch Raúl Castro hơn là các cán bộ Bộ Ngoại giao, và theo kênh CNN trích nguồn từ Cuba, là do Alejandro Castro Espín, con trai của Chủ tịch Raúl đứng đầu. Phía Cuba tới với bàn đàm phán với chỉ một ưu tiên duy nhất: Các điệp viên của họ phải được trao trả - đặc biệt là Gerardo Hernández, người đang thụ hai án chung thân do từng cung cấp những thông tin dẫn tới việc Cuba bắn hạ hai máy bay của nhóm lưu vong Hermanos al Rescate tại Mỹ vào năm 1996. Nhưng sau vài cuộc họp ban đầu, họ dần hé lộ ý định đề cập tới một chương trình trọn bộ gồm cả việc ngừng các chương trình “khuyến khích dân chủ” của Mỹ; trả lại Cuba căn cứ hải quân Guantánamo, và đưa Cuba ra khỏi danh sách các nước bảo trợ khủng bố của Bộ Ngoại giao Mỹ.

Trong khi đó Ricardo Zuniga và Benjamin Rhodes đến với các cuộc đàm phán với một cách tiếp cận uyển chuyển hơn. Theo lời một quan chức Nhà Trắng nắm rõ tiến trình này thì “chúng tôi không có một ý tưởng cố định về điều mình muốn trong một thỏa thuận. Thay vào đó là việc thử nghiệm những công thức khác nhau để tìm ra có thể thỏa thuận được gì. Chưa bao giờ chúng tôi nghĩ rằng đó sẽ là một điều gì to tát”.

Tuy nhiên, Nhà Trắng đã dự trù từ ban đầu rằng việc tái thiết lập quan hệ ngoại giao chính thức sẽ là một phần của thỏa thuận cuối cùng, nếu như hai bên tiến tới được thỏa thuận đó, vì giá trị biểu tượng của bước đi ấy. Nếu tất cả những gì đạt được chỉ là việc trao đổi tù nhân và một vài điều chỉnh những quy định về đi lại và thương mại, sẽ chẳng ai coi sáng kiến của ông Obama là một sự thay đổi chính sách. Do việc xóa bỏ cấm vận đã bị luật hóa và không còn nằm trong tầm tay của tổng thống, việc khôi phục quan hệ ngoại giao là điều duy nhất có thể làm để đánh dấu sự dứt bỏ quá khứ.

Êkíp của Mỹ muốn tránh đàm phán một loạt bước đi theo kiểu “ăn miếng trả miếng” vì bản thân họ muốn thay đổi cách tiếp cận từng nhiều lần thất bại trong quá khứ này. Cũng theo nhân chứng là quan chức Nhà Trắng trên, các phiên đàm phán ban đầu mang nặng tính thăm dò, hai bên muốn nắm bắt những ý đồ chính thật sự của bên kia. Khi cả hai bên đều đã bày tỏ quan điểm của mình, sự bất đồng là rất rõ ràng. Đội ngũ của Mỹ không hề sẵn sàng nói về các chương trình khuyến khích dân chủ hay Guantánamo, trong khi phía Cuba không muốn đả động tới việc các can phạm của Mỹ ẩn náu tại Cuba hay nhân quyền. Đề tài duy nhất mà cả hai bên sẵn lòng thảo luận chỉ là trao đổi tù nhân và với thời gian, các cuộc đối thoại chỉ tập trung vào vấn đề này.

Ngay từ đầu, nhóm đàm phán của Mỹ đã tỏ ra cứng rắn: Việc mở cửa quan hệ ngoại giao chỉ có thể khả thi nếu Cuba phóng thích Alan Gross. Phía Cuba cũng sẵn lòng làm điều này… nhưng chỉ khi Mỹ thả ba thành viên còn bị giam giữ của “bộ ngũ”. Cũng giống như các cuộc thương lượng giữa hai Bộ Ngoại giao trước đó, cuộc trao đổi này là bất khả thi trong con mắt của Nhà Trắng. Tổng thống Mỹ từng lặp lại nhiều lần rằng Gross bị bỏ tù một cách bất công khi không làm điều gì xấu cả, rằng ông không phải là một điệp viên và do vậy không thể trao đổi với điệp viên. Nhưng đối với phía Cuba, Gross là một mật vụ chìm đã tham gia vào một chương trình nhằm lật đổ chính phủ của họ. Sự bất đồng trong việc đánh giá tương xứng hay không giữa Gross và ba điệp viên Cuba đã làm ngừng tiến trình trong suốt năm 2013, như đã từng làm tê liệt quá trình cải thiện quan hệ song phương kể từ khi nhà thầu USAID bị bắt giữ. 

Đề xuất ban đầu của phía Mỹ để đổi lấy sự phóng thích Alan Gross là một loạt các biện pháp nhưng không kèm việc trả tự do cho ba tình báo Cuba. Nhưng những người Cuba lại xuất phát từ cơ sở tối thiểu là “thỏa thuận cứng”: Gross đổi Hernández. Khi các đề xuất của hai bên lâm vào ngõ cụt không lối thoát, thì “vấn đề Sarraff Trujillo” xuất hiện và làm thay đổi cục diện.

Trong một cuộc gặp bí mật tại Toronto vào tháng 1/2014, phía Mỹ đã gợi ý một công thức khá hấp dẫn về mặt chính trị để giành lại Alan Gross và trao trả ba điệp viên Cuba cho La Habana mà không phải qua hình thức trao đổi trực tiếp: Nếu La Habana thả Gross vì lý do nhân đạo, Washington sau đó sẽ trao đổi ba tình báo Cuba lấy một điệp viên cụ thể, Rolando Sarraff Trujillo, một “chuột trũi” quan trọng của CIA trong lòng cộng đồng tình báo Cuba. Sarraff chính là người đã cung cấp thông tin cần thiết để Mỹ bắt giữ và kết án các điệp viên chìm của Cuba như Ana Montes, tại CIA; Walter Kendall Myers, tại Bộ Ngoại giao Mỹ; và nghịch lý là cả chính mạng lưới tình báo của “bộ ngũ”. Sarraff bị Cuba phát hiện và bắt giam từ giữa những năm 1990 và giờ đây CIA muốn chuộc lại tự do của y bằng chính những điệp viên mà hắn đã lật tẩy. Nhưng Sarraff quá quan trọng và phía Cuba không muốn từ bỏ, và như lời chia sẻ của một quan chức Nhà Trắng trên tuần báo Newsweek, điều này tiếp tục làm chậm và thậm chí hơn một lần suýt chút nữa chấm dứt luôn các cuộc đàm phán.

Một ngõ cụt khác của cuộc đối thoại xuất hiện vào tháng 5/2014, khi chính quyền của ông Obama công bố một cuộc trao đổi tù nhân khác: Mỹ phóng thích 5 thủ lĩnh cao cấp của Taliban để đổi lại tự do của hạ sĩ Mỹ Bowe Bergdahl, người bị Taliban tại Afganistan bắt và giam giữ từ năm 2009. Sự bất cân xứng trong vụ trao đổi này gần như trở thành một bê bối chính trị tại Quốc hội và trên các phương tiện truyền thông. Xét tới cái giá chính trị quá lớn phải trả trong vụ Bergdahl, một trao đổi tương tự với Cuba sẽ gặp rất nhiều vấn đề. Nhưng những người Cuba lại nhìn nhận sự việc theo cách khác: Nếu Mỹ có thể đổi năm thủ lĩnh Taliban chỉ lấy một lính Mỹ, thì rốt cục Nhà Trắng cũng có thể đổi ba điệp viên của họ lấy Alan Gross. 

Trong cuộc họp bí mật vào tháng 6/2014, Rhodes và Zuniga đã phải thuyết phục phía Cuba rằng sự việc trước đó chỉ càng cho thấy “các vụ trao đổi tù binh có thể gây tranh cãi tới nhường nào” và do đó họ “chỉ có thể tính tới một sự trao đổi tù nhân phù hợp”, có nghĩa là đổi ba điệp viên Cuba lấy Sarraff. Rhodes và Zuniga cũng đề nghị hướng tới một tầm nhìn vấn đề rộng lớn hơn, hay nói cách khác là một bước cải thiện về chất trong quan hệ hai nước mà La Habana từng chờ đợi trong thời gian dài.