Exhibit 5.1

[Gibson, Dunn & Crutcher LLP Letterhead]

March 12, 2018

Capital One Financial Corporation

1680 Capital One Drive

McLean, Virginia 22102

Re: Capital One Financial Corporation

Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to Capital One Financial Corporation, a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) of a Registration Statement on Form S-3 (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the registration under the Securities Act and the proposed issuance and sale from time to time pursuant to Rule 415 under the Securities Act, together or separately and in one or more series (if applicable) of:

(i) the Company’s unsecured debt securities, which may either be senior debt securities (“Senior Debt Securities”) or subordinated debt securities (the “Subordinated Debt Securities” and, collectively with the Senior Debt Securities, the “Debt Securities”);

(ii) shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”);

(iii) shares of the Company’s preferred stock, par value $0.01 per share (the “Preferred Stock”);

(iv) depositary shares each representing a fraction of a share of a particular series of Preferred Stock (the “Depositary Shares”);

(v) contracts for the purchase or sale of Debt Securities, Preferred Stock or Common Stock or other securities, currencies or commodities (the “Purchase Contracts”);

(vi) warrants for the purchase of Common Stock, Preferred Stock, Depositary Shares or Debt Securities (the “Warrants”); and

(vii) units of the Company comprised of any combination of Common Stock, Preferred Stock, Depositary Shares, Purchase Contracts or Debt Securities (the “Units”).

The Debt Securities, Common Stock, Preferred Stock, Depositary Shares, Purchase Contracts, Warrants, and Units are collectively referred to herein as the “Securities.” The Senior Debt Securities are to be issued under an indenture (the “Senior Indenture”) between the Company and

Capital One Financial Corporation

March 12, 2018

Page 2

The Bank of New York Mellon Trust Company, N.A., formerly known as The Bank of New York Trust Company, N.A. (as successor to Harris Trust and Savings Bank), as trustee. The Subordinated Debt Securities are to be issued under an indenture (the “Subordinated Indenture,” and together with the Senior Indenture, the “Base Indentures”) between the Company and The Bank of New York Mellon Trust Company, N.A., as indenture trustee.

In arriving at the opinions expressed below, we have examined originals, or copies certified or otherwise identified to our satisfaction as being true and complete copies of the originals, of forms of the Base Indentures, forms of the Debt Securities, specimen Common Stock certificates and such other documents, corporate records, certificates of officers of the Company and of public officials and other instruments as we have deemed necessary or advisable to enable us to render these opinions. In our examination, we have assumed the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to original documents of all documents submitted to us as copies. As to any facts material to these opinions, we have relied to the extent we deemed appropriate and without independent investigation upon statements and representations of officers and other representatives of the Company and others.

We have assumed without independent investigation that:

(i) at the time any Securities are sold pursuant to the Registration Statement (the “Relevant Time”), the Registration Statement and any supplements and amendments thereto (including post-effective amendments) will be effective and will comply with all applicable laws;

(ii) at the Relevant Time, a prospectus supplement will have been prepared and filed with the Commission describing the Securities offered thereby and all related documentation and will comply with all applicable laws;

(iii) all Securities will be issued and sold in the manner stated in the Registration Statement and the applicable prospectus supplement;

(iv) at the Relevant Time, all corporate or other action required to be taken by the Company to duly authorize each proposed issuance of Securities and any related documentation (including (i) the due reservation of any shares of Common Stock or Preferred Stock for issuance upon exercise, conversion or exchange of any Securities for Common Stock or Preferred Stock (a “Convertible Security”), and (ii) the execution (in the case of certificated Securities), delivery and performance of the Securities and any related documentation referred to in paragraphs 1 through 7 below) shall have been duly completed and shall remain in full force and effect;

(v) upon issuance of any Common Stock or Preferred Stock, including upon exercise, conversion or exchange of any Convertible Security, the total number of shares of Common Stock or Preferred Stock issued and outstanding will not exceed the total number of shares of Common Stock or Preferred Stock, as applicable, that the Company is then authorized to issue under its certificate of incorporation and other relevant documents;

Capital One Financial Corporation

March 12, 2018

Page 3

(vi) in the case of Debt Securities, at the Relevant Time, the relevant Base Indenture shall have been qualified under the Trust Indenture Act of 1939, as amended; and

(vii) at the Relevant Time, a definitive purchase, underwriting or similar agreement and any other necessary agreement with respect to any Securities offered or issued will have been duly authorized by all necessary corporate or other action of the Company and duly executed and delivered by the Company and the other parties thereto.

Based on the foregoing and in reliance thereon, and subject to the assumptions, exceptions, qualifications and limitations set forth herein, we are of the opinion that:

1. With respect to any Debt Securities, when:

a. the terms and conditions of such Debt Securities have been duly established by supplemental indenture or officers’ certificate in accordance with the terms and conditions of the relevant Base Indenture,

b. any such supplemental indenture has been duly executed and delivered by the Company and the relevant trustee (together with the relevant Base Indenture, the “Indenture”), and

c. such Debt Securities have been executed (in the case of certificated Debt Securities), delivered and authenticated in accordance with the terms of the applicable Indenture and issued and sold for the consideration set forth in the applicable definitive purchase, underwriting or similar agreement,

such Debt Securities will be legal, valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

2. With respect to any shares of Preferred Stock, when:

a. the certificate of designations relating to such Preferred Stock (the “Certificate of Designations”) has been duly executed and filed with the Office of the Secretary of State of the State of Delaware,

b. such shares have been issued either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement and for the consideration therefor provided for therein or (ii) upon exercise, conversion or exchange of any Convertible Security and for any additional consideration specified in such Convertible Security or the instrument governing such Convertible Security providing for such conversion or exercise, which consideration (including any consideration paid for such Convertible Security), on a per-share basis, shall in either event not be less than the par value of the Preferred Stock, and

c. any such Convertible Security was previously validly issued and is fully paid an non-assessable (in the case of an equity Security) or is a legal, valid and binding obligation of the Company, enforceable against the Company in accordance with its terms,

Capital One Financial Corporation

March 12, 2018

Page 4

such shares of Preferred Stock will be validly issued, fully paid and non-assessable.

3. With respect to Depositary Shares, when:

a. a deposit agreement relating to such Depositary Shares (“Deposit Agreement”) has been duly executed and delivered by the Company and the depositary appointed by the Company,

b. the terms of the Depositary Shares have been established in accordance with the Deposit Agreement, and

c. the depositary receipts representing the Depositary Shares have been duly executed and countersigned (in the case of certificated Depositary Shares), registered and delivered in accordance with the related Deposit Agreement and the applicable definitive purchase, underwriting or similar agreement for the consideration provided therein, the depositary receipts evidencing the Depositary Shares will be legal, valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

4. With respect to shares of Common Stock, when:

a. such shares of Common Stock have been duly executed (in the case of certificated shares) and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement for the consideration provided for therein, or (ii) upon conversion or exercise of any Convertible Security, in accordance with the terms of such Convertible Security or the instrument governing such Convertible Security providing for such conversion or exercise, and for any additional consideration specified therein, which consideration (including any consideration paid for such Convertible Security), on a per-share basis, shall in either event not be less than the par value of the Common Stock, and

b. any such Convertible Security was previously validly issued and is fully paid and non-assessable (in the case of an equity Security) or is a legal, valid and binding obligation of the Company, enforceable against the Company in accordance with its terms,

such shares of Common Stock will be validly issued, fully paid and non-assessable.

Capital One Financial Corporation

March 12, 2018

Page 5

5. With respect to any Purchase Contracts, when:

a. the related purchase contract agreement (“Purchase Contract Agreement”), if any, has been duly executed by the Company and each other party thereto,

b. the terms of the Purchase Contracts have been established in accordance with the Purchase Contract Agreement, if any, or the applicable definitive purchase, underwriting or similar agreement,

c. the terms of any collateral or security arrangements relating to such Purchase Contracts have been established and the agreements thereto have been validly executed and delivered by each of the parties thereto and any collateral has been deposited with the collateral agent, if applicable, in accordance with such arrangements, and

d. such Purchase Contracts have been executed (in the case of certificated Purchase Contracts) and delivered in accordance with the Purchase Contract Agreement, if any, and the applicable definitive purchase, underwriting or similar agreement for the consideration provided for therein,

such Purchase Contracts will be legal, valid and binding obligations of the Company, enforceable in accordance with their terms.

6. With respect to any Warrants, when:

a. the warrant agreement relating to such Warrants (the “Warrant Agreement”), if any, has been duly executed and delivered by the Company and each other party thereto,

b. the terms of the Warrants have been established in accordance with the Warrant Agreement, if any, and the applicable definitive purchase, underwriting or similar agreement, and

c. the Warrants have been duly executed (in the case of certificated Warrants) and delivered in accordance with the Warrant Agreement, if any, and the applicable definitive purchase, underwriting or similar agreement for the consideration provided for therein,

such Warrants will be legal, valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

Capital One Financial Corporation

March 12, 2018

Page 6

7. With respect to any Units, when:

a. the unit agreement relating to the Units (the “Unit Agreement”), if any, has been duly executed and delivered by the Company and each other party thereto,

b. the terms of the Units have been duly established in accordance with the Unit Agreement, if any, and the applicable definitive purchase, underwriting or similar agreement, and

c. the Units have been duly executed (in the case of certificated Units) and delivered in accordance with the Unit Agreement, if any, and the applicable definitive purchase, underwriting or similar agreement for the consideration provided for therein,

the Units will be legal, valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

The opinions expressed above are subject to the following exceptions, qualifications, limitations and assumptions:

A. We render no opinion herein as to matters involving the laws of any jurisdiction other than the State of New York and to the extent relevant for our opinions herein, the Delaware General Corporation Law. This opinion is limited to the effect of the current state of the laws of the State of New York and the Delaware General Corporation Law and the facts as they currently exist. We assume no obligation to revise or supplement this opinion in the event of future changes in such laws or the interpretations thereof or such facts.

B. The opinions above (other than those in paragraphs 2 and 4) are each subject to (i) the effect of any bankruptcy, insolvency, reorganization, moratorium, arrangement or similar laws affecting the rights and remedies of creditors’ generally, including the effect of statutory or other laws regarding fraudulent transfers or preferential transfers, and (ii) general principles of equity, including concepts of materiality, reasonableness, good faith and fair dealing and the possible unavailability of specific performance, injunctive relief or other equitable remedies regardless of whether enforceability is considered in a proceeding in equity or at law.

C. We express no opinion regarding the effectiveness of (i) any waiver of stay, extension or usury laws or of unknown future rights or (ii) provisions relating to indemnification, exculpation or contribution, to the extent such provisions may be held unenforceable as contrary to public policy or federal or state securities laws.

D. To the extent relevant to our opinions in paragraphs 3, 5, 6 and 7 and not covered by our opinions in paragraphs 1, 2 or 4, we have assumed that any securities, currencies or commodities underlying, comprising or issuable upon exchange, conversion or exercise of any Depositary Shares, Purchase Contracts, Warrants, or Units are validly issued, fully paid and non-assessable (in the case of an equity security) or a legal, valid and binding obligation of the issuer thereof, enforceable against such issuer in accordance with its terms.

Capital One Financial Corporation

March 12, 2018

Page 7

You have informed us that you intend to issue Securities from time to time on a delayed or continuous basis, and we understand that prior to issuing any Securities pursuant to the Registration Statement (i) you will advise us in writing of the terms thereof, and (ii) you will afford us an opportunity to (x) review the operative documents pursuant to which such Securities are to be issued or sold (including the applicable offering documents), and (y) file such supplement or amendment to this opinion (if any) as we may reasonably consider necessary or appropriate.

We consent to the filing of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption “Certain Legal Matters” in the Registration Statement and the prospectus that forms a part thereof. In giving these consents, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Gibson, Dunn & Crutcher LLP