Are Starfleet vessels allowed to travel freely in Klingon space?

Question

Inspired by this question...

As shown in the map above, the Federation is rather "landlocked" in the 24th Century. Starfleet's general continuing mission is "to explore strange new worlds, to seek out new life and new civilizations, to boldly go where no one has gone before." The Cardassians, the Breen, the Tholians, and the Romulans are blocking off quite a bit of potential exploring space.

In times of peace, can Starfleet ships travel through and explore beyond the "back fence" of the Klingon Empire?

Answer 1

Yes or no, depending on the era

If your core question is whether or not Starfleet vessels are free to travel through Klingon space, then the answer depends heavily on the time period, as the nature of relations between the Federation and the Klingon Empire evolves greatly over time.

Archer's time

In Archer's time (during which Starfleet existed but the Federation did not, at least not yet), there were no formal relations between Earth and the Klingon Empire, yet no open hostilities either. In the first episode "Broken Bow", Archer's Enterprise was allowed to travel as far as the Klingon homeworld of Qo'noS in order to return a Klingon citizen to the Empire, but permission to enter Klingon space was brokered by the Vulcans through diplomatic channels.

It is doubtful that Archer could have entered Klingon territory without those diplomatic discussions. For instance, a Tellerite bounty hunter learned the hard way that Klingon space is not open to outsiders, as recounted in the Enterprise Season 2 episode "Bounty":

SKALAAR: My brother and I were hauling a shipment of fire-salt. I thought I could trim two or three days off our journey by cutting across the most insignificant corner of Klingon space. I learned very quickly there's no such thing as an insignificant corner of Klingon space. We were lucky to escape with our lives, though we did pay a price.

Kirk's time

In Kirk's time (the 23rd Century), relations had degenerated into periods of both open and implicit warfare between the Federation and the Empire, including the establishment of a "Neutral Zone" between their territories which was not dismantled until the Khitomer Accord, whose negotiations began in Star Trek VI: The Undiscovered Country. Generally speaking, during Kirk's time as captain, no Starfleet ship could travel freely into Klingon space without facing armed conflict.

(Above: Colonel West, as depicted in The Undiscovered Country, presenting a plan to the Federation President for sneaking into the Klingon Empire to rescue Kirk and McCoy from the prison at Rura Penthe.)

TNG-era

In the TNG-era, we witness post-Khitomer relations between the Empire and the Federation. The Neutral Zone has been dismantled by this time (not to be confused with the Neutral Zone between the Romulan Star Empire and the Federation, which persisted) and there are diplomatic relations between the two powers (although this was disrupted for a short time during DS9).

During the peace, it seems that Starfleet vessels had some liberty to travel into the Empire. For instance, in TNG "Sins of the Father", Picard orders a sudden course change direct to Qo'noS:

PICARD: We're changing course. Set coordinates for the First City of the Klingon Imperial Empire.

(Let's not get started about "Imperial Empire"....)

Of course, they may have made their intentions known after the course change by contacting the Klingon High Command directly, although such dialogue does not occur on screen. If they had, then their request to travel was not denied. In any case, they were able to make their way to Qo'noS unimpeded.

Also, there is dialogue mentioning a Klingon ship in Federation space under routine circumstances. In "A Matter of Honour", while the Enterprise is docked at a Federation Starbase, we hear the following:

PICARD: It's been suggested that an officer from the Enterprise might participate in the [exchange] programme.

RIKER: That's probably a good idea.

PICARD: Well, there is a Klingon vessel in the area.

RIKER: I don't recall hearing of a Federation officer serving ever on a Klingon vessel.

Answer 2

No. But remember: Space is BIG. And three dimensional.

The assumption on maps like that is that territorial claims run along the border perpendicular to the axis of the galaxy through the entire disc. On average, the galaxy is 1000ly thick. According to the scale on the map, 1000 ly compares favorably to the thickness of the major powers. It's POSSIBLE that the claims run vertically by treaty, but it's more likely that the actual sovereign territories are blobby rounded shapes, not thick pucks of space.

Now, the Federation plays fair, so they would diplomatically request traversal in Klingon space... but the "Sovereign" territory of the Federation itself contains PLENTY of stuff that still needs to be explored. They've only been doing it for a few hundred years. The sovereign territory of the Federation basically involves saying "We control this star, and all the space around it. And there's a lot of it." Anything could be in "Federation" space which may not necessary respect Federation sovereignty, and there's plenty of stuff they don't even know about, like the Dyson Sphere.

Should the Federation run out of space, they'll request a route through Klingon space, or they'll just fly around it.