In the days before Performance Based Navigation (PBN), countries would specify a track keeping accuracy needed to fly a route and you would certify that you had the right equipment to do just that. The standard was "sensor based." PBN systems must be able to monitor their own performance and alert the crew when there are problems. B-RNAV comes from before PBN but is still in use throughout Europe; you need to have it if you fly there. Under 14 CFR 91 you will need an AFM statement, under 14 CFR 135 you will need OpSpec B034.
What follows comes from the references shown below. Where I think it helpful, I've added my own comments in blue.
[ICAO Doc 7030, §EUR, ¶22.214.171.124.2] Precision RNAV (P-RNAV) and basic RNAV (B-RNAV)
126.96.36.199.2.1 The provisions in respect of en-route operations, as specified in 188.8.131.52.2.6 and 184.108.40.206.2.7, shall apply to all such operations conducted under IFR on the entire ATS route network as notified by the appropriate authorities in the following flight information regions (FIRs)/upper flight information regions (UIRs):
Amsterdam, Ankara, Athinai, Barcelona, Berlin, Bodø, Bordeaux, Bratislava, Bremen, Brest, Brindisi, Bruxelles, Bucuresti, Budapest, Canarias (AFI area of applicability), Casablanca, Chisinau, Düsseldorf, France, Frankfurt, Hannover, Istanbul, Kharkiv, København, Kyiv, Lisboa, Ljubljana, London, L'viv, Madrid, Malta, Marseille, Milano, München, Nicosia, Odessa, Oslo, Paris, Praha, Reims, Rhein, Riga, Roma, Rovaniemi, Scottish, Shannon, Simferopol, Skopje, Sofia, Stavanger, Sweden, Switzerland, Tallinn, Tampere, Tbilisi, Tirana, Trondheim, Tunis (FL 245 and above), Varna, Vilnius, Warszawa, Wien, Yerevan, Zagreb.
220.127.116.11.2.6 Only aircraft approved for B-RNAV operations may plan for operations under IFR on the ATS routes of the FIRs/UIRs identified in 18.104.22.168.2.1. Aircraft not equipped with RNAV but having a navigation accuracy meeting RNP 5 will be restricted to operations on ATS routes which States may designate within their lower airspace in accordance with 22.214.171.124.2.7.
126.96.36.199.2.7 Until such time as VOR facilities cease to be available, the carriage of a single RNAV system not meeting an average continuity of service of 99.99 per cent of flight time may be approved for B-RNAV operations if the aircraft is also carrying VOR and distance-measuring equipment (DME) equipment.
There are exceptions, but for the most part, if you fly in Europe you will need B-RNAV.
[AC 90-96A, ¶4.b.] Basic Area Navigation (B-RNAV). B-RNAV is defined as RNAV that meets a track keeping accuracy equal to or better than +/-5 NM for 95 percent of the flight time. This value includes signal source error, airborne receiver error, display system error, and flight technical error. This navigation performance assumes the necessary coverage provided by satellite or ground-based navigation aids is available for the intended operation.
[ICAO Doc 9613 ¶188.8.131.52] The performance-based navigation (PBN) concept specifies that aircraft RNAV system performance requirements be defined in terms of accuracy, integrity, availability, continuity and functionality required for the proposed operations in the context of a particular airspace concept, when supported by the appropriate navigation infrastructure. In that context, the PBN concept represents a shift from sensor-based to performance-based navigation. Performance requirements are identified in navigation specifications, which also identify the choice of navigation sensors and equipment that may be used to meet the performance requirements. These navigation specifications provide specific implementation guidance for States and operators in order to facilitate global harmonization.
[ICAO Doc 9613 ¶184.108.40.206] On-board performance monitoring and alerting is the main element that determines if the navigation system complies with the necessary safety level associated to an RNP application; it relates to both lateral and longitudinal navigation performance; and it allows the aircrew to detect that the navigation system is not achieving, or cannot guarantee with 10–5 integrity, the navigation performance required for the operation.
What we have grown up with, accuracy standards, specify what it takes to fly the airspace in question and permit properly equipped aircraft and trained crews to fly there. Performance Based Navigation, on the other hand, mandates a performance standard which includes navigation accuracy but also includes other parameters, such as the ability to self monitor and alert the crew of integrity issues.
B-RNAV is an accuracy standard that lives in a middle ground, as the PBN manual states:
[ICAO Doc 9613 ¶220.127.116.11.2] In the past, the United States and member States of the European Civil Aviation Conference (ECAC) used regional RNAV specifications with different designators. The ECAC applications (P-RNAV and B-RNAV) will continue to be used only within those States. Over time, ECAC RNAV applications will migrate towards the international navigation specifications of RNAV 1 and RNAV 5. The United States migrated from the USRNAV Types A and B to the RNAV 1 specification in March 2007.
[AC 90-96A, Appendix 1 ¶1.b.(1)] The aircraft should be considered eligible for B-RNAV operations, if the AFM or POH shows the appropriate instrument flight rules (IFR) navigation system installation has received airworthiness approval in accordance with this advisory circular (AC) or with one of the following Federal Aviation Administration (FAA) ACs: AC 90-45A, AC 20-121A, AC 20-130, AC 20-138, or AC 25-15.
[AC 90-96A, Appendix 1 ¶1.b.(2)] U.S. part 91 operators should review their AFM or POH to ensure aircraft system eligibility as detailed in Appendix 1, paragraph 1b(1). Once aircraft system eligibility has been established, the operator should take steps to ensure B-RNAV operations are conducted in accordance with the guidance contained in Appendix 1, paragraph 1d, 2, 3, and 4, as well as any other established operational or airspace requirements. Operators must ensure the required functions of Appendix 1 are met. Once these actions are completed, the operator may begin to conduct B-RNAV operations. A letter of authorization (LOA) is not required when eligibility is based on the AFM or POH. See Appendix 1, paragraph 1c, for actions to take if the operator is unable to determine from the AFM or POH whether the aircraft system has been approved and installed in accordance with an appropriate FAA AC.
If your AFM or POH has the necessary statement, you have what you need to operate B-RNAV under 14 CFR 91. (An LOA is not needed.) Otherwise, there are other means listed in AC 90-96A to get approval.
[AC 90-96A, Appendix 1 ¶1.b.(3)] Part 121, 125, or 135 operators should present the following documentation to their certificate-holding district office (CHDO): sections of the AFM that document airworthiness approval in accordance with an appropriate FAA AC as detailed in Appendix 1, paragraph 1b(1) and training and operations manuals that reflect the operating policies of Appendix 1, paragraph 1d, 2, 3, 4 as well as any other operational or airspace requirements established by European authorities. Operators must ensure the required functions of Appendix 1 are met.
[FAA Order 8900.1, Vol 3, Chapter 18, OPSEC B034, ¶B.] B034 also authorizes an operator to conduct IFR operations in designated European Basic RNAV (B-RNAV) and European Precision RNAV (P-RNAV) airspace.
If your AFM or POH has the necessary statement, you have what you need to apply for OpSpec B034 under 14 CFR 135. Otherwise, there are other means listed in AC 90-96A to get approval.
Figure: Limitations Extract, from G450 Airplane Flight Manual, §1-03-10, ¶13.]
Under 14 CFR 91, if you have a similar statement in your AFM or POH, you are good to go.
Under 14 CFR 135, you will also need OpSpec B034:
Figure: Example OpSpec B034, from Eddie's sordid past.
Portions of this page can be found in the book International Flight Operations, Part III, Chapter 6.
Advisory Circular 90-96A, Approval of U.S. Operators and Aircraft to Operate Under Instrument Flight Rules (IFR) in European Airspace Designated for Basic Area Navigation (B-RNAV) and Precision Area Navigation (P-RNAV), 1/13/05, U.S. Department of Transportation
Advisory Circular 91-70A, Oceanic and International Operations, 8/12/10, U.S. Department of Transportation
Gulfstream G450 Airplane Flight Manual, Revision 36, December 5, 2013
ICAO Doc 7030 - Regional Supplementary Procedures, International Civil Aviation Organization, 2008
ICAO Doc 9613 - Performance Based Navigation (PBN) Manual, International Civil Aviation Organization, 2008