That one comes from:
te-form of なくす - to lose smth. + しまう - to do something by accident; to finish completely
You attach しまう to a te-form to express an action that is done or happened unintentionally. Mostly with a slightly negative connotation to it.
So your expression actually means "I lost unwillingly/unintentionally (...)"