Not exactly a SSM but very, very close: in Denmark "civil union" or "registered partnership" was allowed in 1989 - see wikipedia:
A civil union, also referred to as a civil partnership, is a legally recognized form of partnership similar to marriage. Beginning with Denmark in 1989, civil unions under one name or another have been established by law in many developed countries in order to provide same-sex couples rights, benefits, and responsibilities similar (in some countries, identical) to opposite-sex civil marriage.
In Denmark, there are still some differences between an ordinary marriage and registered partnership, e.g. in regard to adoption and in heritage...
UPDATE: Today - 2012-06-07 - we have actually adopted a new law that will fully allow SSM and not just registered partnerships. [L106 in Danish]