Right way to initialize python embedded in a multi-threaded application

[shooshx]

I'm embedding python in a multi-threaded C application.
I've taken care to wrap every call to the Python C API with

gstate = PyGILState_Ensure();
// call python code
PyGILState_Release(gstate);

But I'm stumped with what to do in the initialization.
Right after the call to Py_IsInitialized() I've added a call:

PyEval_InitThreads();

The docs say that this function leaves the GIL locked when it returns.
I do some more initializations like importing modules and then I call

PyEval_ReleaseLock();

This seems to cause a problem since not long after a call to
PyGILState_Release(gstate) that's made in a different thread crashes.
with

"Fatal Python error: This thread state must be current when releasing"

If I don't do the call to PyEval_ReleaseLock() in the main thread
right after initialization, the GIL seems to be released
after the first PyGILState_Ensure() - PyGILState_Release() pair.

So what am I doing wrong here?
What is the correct way of initializing a multi-threaded application?