Does this mean that the person remembered the person's face from seeing it somewhere before this moment or that he had his face memorized just now? There isn't context to it so I'm not sure. Can it go both ways?
覚える (oboeru) means to memorize, 思い出す(omoidasu) means to recall. So the sentence means "I memorized (at least) his face (just now)."
By the way, how come a sentence like this doesn't have a context? Is this a song title or such?