It doesn't necessarily mean a romantic relationship. It often does, but the usage implies that there was something negative between you.
If I ended a relationship with a woman on good terms I might say
We used to date
But if it was a torrid affair that interfered with my life and friendships, but I don't want to expound upon it I would say
We have a history
Outside of a romantic context, say I had a long-term business rival who I frequently came into conflict with, "we have a history" is also appropriate.
But I would not use that phrase to refer to a long-term friendship or familial relationship.