trouble w/ pushing commits -- "failed to push some refs"

Hi,

I've made several commits to my local Git repo (hope I'm
using the right terminology there) and I am trying to push them.
When I try

  git push origin master

I get this message:

To ssh://robert_dodier at maxima.git.sourceforge.net/gitroot/maxima/maxima
 ! [rejected]        master -> master (non-fast forward)
error: failed to push some refs to
'ssh://robert_dodier at maxima.git.sourceforge.net/gitroot/maxima/maxima'

I gather the stuff I have is out of date wrt the SF repo, right?
Now how shall I resolve that -- I gather that I could rebase,
but that would throw away the history, which I'd rather not
have to recreate. How can I bring my repo up to date without
throwing away the commit history? Or maybe it's actually
some other problem?

Thanks for any info. Yes, I have browsed various manuals
and tutorials and I still don't understand what's going on.
Sorry about that.

best

Robert Dodier