Toenmalig kroonprins [[Paul I van Griekenland]] deed Frederika een huwelijksaanzoek gedurende de [[Olympische SpelenZomerspelen 1936|Olympische SpelenZomerspelen van 1936]] in [[Berlijn]]. Prins Paul was een zoon van de Griekse koningin [[Constantijn I van Griekenland]] en [[Sophie van Pruisen]], zuster van de Duitse keizer [[Wilhelm II van Duitsland|Wilhelm II]]. Paul en Frederika waren allebei afstammeling van koningin [[Victoria van het Verenigd Koninkrijk|Victoria]]. Paul was een achterkleinzoon van de Britse koningin en Frederika was een achter-achterkleindochter van de koningin. Hun verloving werd officieel aangekondigd op 28 september 1937. Ze trouwde op 9 januari 1938 in [[Athene (stad)|Athene]]. Bij het huwelijk kreeg Frederika de titel erfprinses mee, omdat Paul I de opvolger was van zijn kinderloze broer [[George II van Griekenland]].
