In every state, the laws are different in terms of what is considered a legally enforceable marriage, which is really a contract and one that you file with the state (signed by you and your spouse and witnesses). In Florida, the certificate had to be returned to be recorded as the date of the marriage and to bear proof of a legally enforceable marriage. This is why you need a license to marry and why a religious ceremony (solemnization) is simply not enough. In Florida, where no marriage certificate is available, there is a statute that covers the marriage where no certificate is available. The marriage may be proved by affidavit before any officer authorized to administer oaths made by two competent witnesses present at the wedding and saw the ceremony performed. Then you would take that affidavit and file it with the county court (ask the family law clerk or filing office).