Vua Erik XIV của Thụy Điển đích thân quan tâm hơn trong việc theo đuổi cuộc hôn nhân với Nữ hoàng Elizabeth I của nước Anh, nhưng ông đã tìm kiếm một liên minh với Ba Lan và đề nghị em trai Johan, Công tước Phần Lan mai mối. Johan đồng ý, nhưng hỏi em gái của Anna là Catherine. Vì nhiều lý do khác nhau, cuộc mai mối bị trì hoãn. Thêm ba chú rể đã được vua anh đề xuất cho Anna: Hoàng tử Đan Mạch Magnus đang là giám mục, mục sư Livonia Gotthard Kettler và Johan của Thụy Điển. Lúc đầu vua Ba Lan yêu cầu Công tước Johan cưới Anna, nhưng Johan khăng khăng đòi cưới Catherine và tổ chức đám cưới long trọng ở Vilnius. Vua Sigismund hỏi ý kiến Anna về cuộc hôn nhân, công chúa đồng ý và Công tước Thụy Điển đã kết hôn với Catherine vào ngày 4 tháng 10 năm 1562