<PAGE>

                                                                     EXHIBIT 4.3

                                                                  Conformed Copy

                   AMENDED AND RESTATED STOCKHOLDERS AGREEMENT

                  AMENDED AND RESTATED STOCKHOLDERS AGREEMENT, dated as of
December 10, 2003 (this "Agreement"), among (i) Volume Services America
Holdings, Inc., a Delaware corporation (the "Company"), (ii) BCP Volume L.P., a
Delaware limited partnership ("BCP Volume") and BCP Offshore Volume L.P., a
Cayman Islands exempted limited partnership, ("BOCP Volume," and together with
BCP Volume, "Blackstone"), (iii) VSI Management Direct L.P., a Delaware limited
partnership ("Management Direct," and together with Blackstone, the "Blackstone
Group") and (iv) Recreational Services L.L.C., a Delaware limited liability
company ("GE LLC," and together with the Blackstone Group, the "Investors,"
including any successors, assigns and transferees thereof).

                                   BACKGROUND

                  1.       Prior to the initial public offering described below,
the Investors are the beneficial holders of all the outstanding shares of common
stock of the Company, par value $0.01 per share (including any securities issued
or distributed in respect thereof, or in substitution therefor, in connection
with any stock split, dividend, spin-off or combination, or any
reclassification, recapitalization, merger, consolidation, exchange or other
similar reorganization or business combination, "Common Stock").

                  2.       The Company desires to conduct an initial public
offering of its Income Deposit Securities ("IDSs"), representing shares of
Common Stock and an aggregate principal amount of its subordinated notes
("Subordinated Notes") pursuant to a registration statement under the Securities
Act of 1933, as amended (together with the rules and regulations of the SEC
promulgated thereunder) in the United States and pursuant to a long form
prospectus or any amendment or supplement thereto, in the English and French
languages, under applicable securities laws in all the provinces of Canada (the
"IPO").

                  3.       On December 2, 2003, the Company effected a stock
split (the "Stock Split") of 40,919.5305278882 shares of Common Stock for each
share of Common Stock outstanding prior to such Stock Split, so that the
Company's outstanding Common Stock totaled 13,612,829.12 shares as of such date
and, as of the date hereof, the Company will issue 16,785,450 shares of Common
Stock underlying the IDSs in respect of the IPO.

                  4.       The Company, certain Investors and General Electric
Capital Corporation ("GECC") are parties to the Amended and Restated
Stockholders' Agreement, dated as of August 24, 1998, as amended (the "Existing
Stockholders Agreement"), which agreement shall be replaced in its entirety by
this Agreement upon completion of the IPO, and, as of the date hereof, GECC has
consented to the IPO and this Agreement and has agreed not be a party to this
Agreement.

<PAGE>

                                                                               2

                  5.       Upon completion of the IPO, the Company shall
repurchase from the Investors a portion of their shares of Common Stock and the
Investors will retain a portion of their shares of Common Stock.

                  6.       Pursuant to the underwriting agreement among the
Company and CIBC World Markets Corp., UBS Securities LLC, RBC Dain Rauscher
Inc., McDonald Investments Inc., a KeyCorp Company, BMO Nesbitt Burns Inc. and
the other underwriters named therein (collectively, the "Underwriters"), dated
December 4, 2003 (the "Underwriting Agreement"), the Company has agreed to sell
16,785,450 IDSs and has granted the Underwriters an option to purchase up to an
additional 1,678,545 IDSs (the "Over-allotment Option").

                  7.       If the Underwriters exercise their Over-allotment
Option, the Company will repurchase a portion of the remaining shares of Common
Stock held by the Investors.

                  8.       Upon completion of the IPO, the Company, BCP Volume,
BOCP Volume, Management Direct, GE LLC and certain members of management shall
enter into a Registration Rights Agreement (the "Registration Rights Agreement")
with respect to their shares of Common Stock and any IDSs and Subordinated Notes
that the parties to such agreement may hold.

                  NOW THEREFORE, in consideration of the mutual covenants
contained herein and other good and valuable consideration, the receipt and
sufficiency of which are hereby acknowledged, the parties to this Agreement
hereby agree as follows:

                                    ARTICLE I

                      RESTATEMENT, REPURCHASE AND EXCHANGE

         1.1      AMENDMENT AND RESTATEMENT OF EXISTING STOCKHOLDERS' AGREEMENT;
APPROVALS OF IPO TRANSACTIONS.

         (a)      Each party hereto agrees that, upon completion of the IPO, (i)
the Existing Stockholders' Agreement shall be amended and restated and replaced
in its entirety with this Agreement and (ii) the terms of the Existing
Stockholders' Agreement shall cease to be of any effect.

         (b)      Each party hereto consents and agrees to take all action
necessary for the completion of the IPO and the related transactions, including,
without limitation, the execution and delivery of this Agreement and the
Registration Rights Agreement and the transactions contemplated hereby and
thereby, and consents to the Company entering into this Agreement, the
Underwriting Agreement and the Registration Rights Agreement and the
transactions contemplated hereby and thereby.

         (c)      Each party hereto ratifies its prior consent to the
restatement of the certificate of incorporation of the Company and consents to
the amendment and restatement of the by-laws of
<PAGE>

                                                                               3

the Company as approved by the board of directors of the Company, substantially
in the forms as filed by the Company as exhibits to the registration statement
on Form S-1.

         1.2      REPURCHASE OF COMMON STOCK UPON IPO. Upon consummation of the
IPO and in consideration for the payment by the Company of $48,310,593.35, at a
price equal to $7.0583 per share of Common Stock, and the covenants and
agreements herein contained, the parties hereto do hereby agree that the shares
of Common Stock held by BCP Volume, BOCP Volume, Management Direct and GE LLC
will be repurchased by the Company in the amounts described below and each of
BCP Volume, BOCP Volume, Management Direct and GE LLC does hereby agree to
deliver and duly transfer, or cause to be duly delivered and transferred, to the
Company, certificates representing the number of shares of Common Stock held by
each party in the amounts described below, free and clear of all liens,
encumbrances and adverse claims:

<TABLE>
<CAPTION>
Investor              Shares of Common Stock
--------              ----------------------
<S>                   <C>
BCP Volume:                3,230,563.37

BOCP Volume:                 838,085.52

Management Direct:           290,694.68

GE LLC:                    2,485,161.54
</TABLE>

         Simultaneous with such repurchase, the Company shall issue, or cause
the transfer agent for the Common Stock to issue, new share certificates to the
Investors in the name of the Investors representing the shares of Common Stock
held by each Investor after giving effect to the repurchase pursuant to this
Section 1.2 with such legends as specified in this Agreement.

         1.3      REPURCHASE OF COMMON STOCK UPON EXERCISE OF OVER-ALLOTMENT
OPTION. Upon exercise by the Underwriters of the Over-allotment Option and in
consideration for the payment by the Company at a price equal to $8.5344 per
share of Common Stock, and the covenants and agreements herein contained, the
parties hereto do hereby agree that the shares of Common Stock held by BCP
Volume, BOCP Volume, Management Direct and GE LLC in the Company shall be
repurchased by the Company and each of BCP Volume, BOCP Volume, Management
Direct and GE LLC does hereby agree, upon such exercise of the Over-allotment
Option, to deliver and duly transfer, or cause to be duly delivered and
transferred, to the Company, certificates representing the number of shares of
Common Stock held by each party in the amounts described below, free and clear
of all liens, encumbrances and adverse claims:
<PAGE>

                                                                               4

<TABLE>
<CAPTION>
                   Maximum Number of Shares of Common Stock Assuming
Investor                Exercise of Over-Allotment Option in Full
--------                ------------------------------------------
<S>                <C>
BCP Volume:                         1,277,842

BOCP Volume:                          331,502

Management Direct:                    114,983

GE LLC:                               983,000
</TABLE>

         Upon any partial exercise of the Over-Allotment Option, BCP Volume,
BOCP Volume, Management Direct and GE LLC shall sell, and the Company shall
purchase, such pro rata number of shares of Common Stock of each such Investor
as will be purchased by the total proceeds received by the Company in such
partial exercise of the Over-Allotment Option.

         Simultaneous with such repurchase, the Company shall issue, or cause
the transfer agent for the Common Stock to issue, new share certificates to the
Investors in the name of the Investors representing the shares of Common Stock,
if any, held by each Investor after giving affect to the repurchase pursuant to
this Section 1.3 with such legends as specified in this Agreement.

         1.4      TRANSFEREE EXCHANGE; LEGENDS. (a) With respect to any shares
of Common Stock (other than shares subject to repurchase) held by the Investors,
upon any sale of the shares of Common Stock (other than shares subject to
repurchase) held by the Investors, such parties agree with the Company that at
the option of the selling party, upon prior written notice to the Company, the
Company shall exchange with the transferee in such sale a portion of the shares
of Common Stock for an amount of Subordinated Notes such that the number of
shares of Common Stock and amount of Subordinated Notes received by the
transferee of such shares of Common Stock shall make an integral whole number of
IDSs, with the initial exchange rate being one share of Common Stock per $9.30
principal amount of Subordinated Notes (such exchange rate subject to customary
adjustment for adjustments specified in the definition of "Common Stock" set
forth above) and the Company will pay cash at a price of 100% of the principal
amount for any fractional portion of a Subordinated Note if the Subordinated
Notes would not be an integral multiple of $5.70 (which is the principal amount
per Subordinated Note represented by an IDS) so that such fractional portions
need not be issued. The shares of Common Stock subject to exchange pursuant to
this Section 1.4(a) can only be exchanged once by an Investor or any successor
or transferee of an Investor.

         The parties hereto agree that, prior to any sale of shares of Common
Stock in which there will be an exchange of a portion of such shares of Common
Stock for an amount of Subordinated Notes pursuant to this Section 1.4(a), the
following conditions must be met: (i) such sale and exchange shall comply with
applicable laws, including, without limitation, securities laws, laws relating
to the redemption of common stock and laws relating to the issuance of debt,
(ii) such sale and exchange shall occur pursuant to an effective registration
statement in the United States and a receipted prospectus for all the provinces
of Canada, (iii) such sale and exchange will not
<PAGE>

                                                                               5

conflict with or cause a default under any material financing agreement, (iv)
such sale and exchange shall not cause a mandatory suspension of dividends or
deferral of interest under any material financing agreement as of the
measurement date immediately following the proposed sale and exchange date, (v)
the selling party shall have given the Company at least 30 but not more than 60
days advance notice of its desire to effect such sale and exchange and (vi) on
or prior to such sale and exchange, for so long as the Credit Agreement, dated
as of December 10, 2003, among the Company, Volume Services America, Inc., the
guarantor parties thereto, KeyBank National Association, as Administrative
Agent, Fronting Bank and Swingline Lender and the lenders parties thereto (the
"Credit Agreement"), remains outstanding, the selling party shall pay to the
Company from the proceeds of such sale an amount equal to five months interest
on the aggregate principal amount of the Subordinated Notes that the Company has
issued in such exchange (unless such amounts have been otherwise paid by or on
behalf of the selling party), and Volume Services America, Inc. shall deposit
such amount in the cash collateral account maintained under the Credit
Agreement; provided, that the Company shall not be required to effect more than
two (2) such transactions on behalf of the Investors in any 12 month period
(other than a transaction effected pursuant to Article III of the Registration
Rights Agreement) if such transactions would result in a determination that the
Subordinated Notes to be issued require a different CUSIP number than the
Subordinated Notes then outstanding.

                  (b)      A copy of this Agreement and the Registration Rights
Agreement shall be filed with the secretary of the Company and kept with the
records of the Company. Each certificate representing shares of Common Stock
subject to this Agreement shall bear the following legend on the face thereof
(in addition to any legend required by state securities or "blue sky" laws):

         "THE SHARES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED
         UNDER THE SECURITIES ACT OF 1933, AS AMENDED, OR UNDER THE SECURITIES
         LAWS OF ANY STATE AND ARE SUBJECT TO AN AMENDED AND RESTATED
         STOCKHOLDERS AGREEMENT AND REGISTRATION RIGHTS AGREEMENT. A COPY OF
         EACH OF THE STOCKHOLDERS AGREEMENT AND REGISTRATION RIGHTS AGREEMENT IS
         AVAILABLE FOR INSPECTION AT THE COMPANY'S PRINCIPAL OFFICES. NO
         TRANSFER, SALE, ASSIGNMENT, PLEDGE, HYPOTHECATION OR OTHER DISPOSITION
         OF THE SECURITIES represented BY THIS CERTIFICATE MAY BE MADE EXCEPT IN
         ACCORDANCE WITH the PROVISIONS OF THE STOCKHOLDERS AGREEMENT AND
         REGISTRATION RIGHTS AGREEMENT AND (A) PURSUANT TO A REGISTRATION
         STATEMENT EFFECTIVE UNDER THE SECURITIES ACT OF 1933, AS AMENDED, OR
         (B) a TRANSFER, SALE, ASSIGNMENT, PLEDGE, HYPOTHECATION OR OTHER
         DISPOSITION that IS EXEMPT FROM the PROVISIONS OF SECTION 5 OF THE
         SECURITIES ACT OF 1933, AS AMENDED, AND THE RULES AND REGULATIONS
         THEREUNDER and, IF REQUESTED, THE COMPANY MAY REQUIRE PROOF OF SUCH
         EXEMPTION. UPON CERTAIN TRANSFERS OF THE SHARES OF COMMON STOCK
         REPRESENTED BY THIS CERTIFICATE, THE COMPANY SHALL EXCHANGE WITH THE
         TRANSFEREE A CERTAIN AMOUNT OF THE SHARES OF COMMON STOCK FOR THE
         COMPANY'S SUBORDINATED NOTES

<PAGE>

                                                                               6

         PURSUANT TO THE TERMS OF, AND SUBJECT TO THE LIMITATIONS CONTAINED IN,
         THE STOCKHOLDERS AGREEMENT AND REGISTRATION RIGHTS AGREEMENT. THE
         HOLDER OF THIS CERTIFICATE AGREES TO BE BOUND BY ALL oF THE PROVISIONS
         OF SUCH STOCKHOLDERS AGREEMENT AND REGISTRATION RIGHTS AGREEMENT."

         The Company agrees to promptly remove (or cause to be removed) the
legend set forth above and to take such further action to remove any
restrictions on the shares of Common Stock in connection with a transfer that is
pursuant to a registration statement effective under the Securities Act and, if
applicable, a receipted prospectus under applicable Canadian securities laws, or
exempt from such registration or filing both in the United States and, if
applicable, Canada.

                                   ARTICLE II

                         REPRESENTATIONS AND WARRANTIES

         2.1      REPRESENTATIONS AND WARRANTIES OF THE COMPANY. The Company
hereby represents and warrants as follows:

         (a)      Organization, Standing and Power. The Company is a
corporation, duly organized, validly existing and in good standing under the
laws of the State of Delaware. The Company has all requisite power and authority
to own, operate and lease its properties and to carry on its business as
currently conducted, and is qualified or licensed to do business and in good
standing in each jurisdiction in which its ownership or leasing of property or
the conduct of its business requires such licensing or qualification, except
where the failure to so qualify would not, individually or in the aggregate,
have a material adverse effect on the business, condition, financial or
otherwise, or results of operations of the Company and its subsidiaries
considered as a whole (a "Material Adverse Effect").

         (b)      Authority. The Company has all requisite corporate power and
authority to execute and deliver this Agreement and to carry out its obligations
hereunder. The execution and delivery of this Agreement and the performance by
the Company of its obligations hereunder have been duly authorized, and no other
corporate proceeding on the part of the Company or its stockholders is required.
This Agreement has been duly executed and delivered by the Company and, assuming
the due authorization, execution and delivery hereof by the Investors, is a
valid and binding obligation of the Company, enforceable against the Company in
accordance with its terms.

         (c)      No Conflicts. To the best of the Company's knowledge, the
execution and delivery of this Agreement by the Company, the performance by the
Company of its obligations hereunder and the consummation of the transactions to
be performed by the Company contemplated by this Agreement will not (a) conflict
with or result in any breach of any provision of the certificate of
incorporation or by-laws of the Company, (b) conflict with, or result in a
violation or breach of, or constitute (with or without due notice or lapse of
time or both) a default or give rise to any right of termination, cancellation
or acceleration under, any of
<PAGE>

                                                                               7

the terms or conditions of any note, bond, mortgage, indenture, license,
agreement or other instrument or obligation to which the Company or any of its
subsidiaries is a party or by which any of them or any of their properties or
assets may be bound or (c) violate any statute or law, or any rule, regulation,
writ, injunction, judgment, order or decree of any court, administrative agency
or governmental authority binding on the Company or any of its subsidiaries, or
any of their respective properties or assets, excluding from the foregoing
clauses (b) and (c), conflicts, violations, breaches and defaults which,
individually and in the aggregate, would not have a material adverse effect on
the ability of the Company to perform its obligations hereunder.

         (d)      Validity of Stock.

                  (i)      All outstanding shares of the Company's Common Stock
         have been duly authorized and validly issued, are fully paid and
         non-assessable, and have not been issued in violation of any
         pre-emptive rights, and BCP Volume, BOCP Volume, Management Direct and
         GE LLC have acquired valid and marketable title thereto from the
         Company, free and clear of any lien, claim, charge, equity or
         encumbrance of any kind.

                  (ii)     Except for this Agreement, the Underwriting Agreement
         and as otherwise disclosed in each of the U.S. and Canadian prospectus
         relating to the IPO, there is outstanding no security, option, warrant,
         right, call, subscription, agreement, commitment or understanding of
         any nature whatsoever, fixed or contingent, that directly or
         indirectly:

                  (A)      calls for the issuance, sale, pledge or other
                           disposition of any shares of Common Stock or IDSs or
                           of any other capital stock of the Company or any
                           securities convertible into, or other rights to
                           acquire, any such shares or other capital stock of
                           the Company; or

                  (B)      obligates the Company to grant, offer or enter into
                           any of the foregoing; or

                  (C)      relates to the voting or control of such shares of
                           Common Stock or of IDSs or other foregoing
                           securities;

                  provided, however, that the foregoing does not apply to any
         security, option, warrant, right, call, subscription, agreement,
         commitment or understanding relating to the partnership or membership
         interests of any of the Investors.

         (e)      Compliance with Applicable Law. The Company and each of its
subsidiaries are currently in compliance with all applicable laws (whether
statutory or otherwise), rules, regulations, orders, ordinances, judgments,
decrees, writs, requirements and injunctions of all governmental authorities in
such jurisdictions where the Company and its subsidiaries do business, except
where the failure to so comply would not, individually or in the aggregate,
result in a Material Adverse Effect.

         (f)      Consents and Approvals. No authorization, consent, order or
approval of or notice to or filing with, any federal, state, provincial or local
governmental authority is required in connection with the execution, delivery
and performance by the Company of this Agreement

<PAGE>

                                                                               8

or of the performance of its obligations hereunder, except for those required
under U.S. federal securities laws, state "blue sky" laws and/or Canadian
securities laws in connection with the IPO and the Registration Rights
Agreement, except for such authorizations, consents, orders or approvals the
failure of which to obtain would not have a material adverse effect on the
ability of the Company to perform its obligations hereunder.

         2.2      REPRESENTATIONS AND WARRANTIES OF THE INVESTORS. Each of the
Investors hereby, severally and not jointly, represents and warrants as follows:

         (a)      Authority. Each of the Investors has all requisite power and
authority to execute and deliver this Agreement and to perform its obligations
hereunder. The execution and delivery of this Agreement and the performance by
each of the Investors of their obligations hereunder has been duly authorized by
each of the Investors and no other proceeding on the part of any Investor is
required. This Agreement has been duly executed and delivered by the Investors
and, assuming the due authorization, execution and delivery hereof by the
Company, is a valid and binding obligation of the Investors, enforceable against
each of the Investors in accordance with its terms.

         (b)      No Conflicts. The execution and delivery of this Agreement by
each of the Investors, the performance by each of the Investors of their
obligations hereunder and the consummation of the transactions to be performed
by each of the Investors contemplated by this Agreement will not (i) conflict
with or result in any breach of any provision of the organizational documents of
such Investor, (ii) conflict with, or result in a violation or breach of, or
constitute (with or without due notice or lapse of time or both) a default or
give rise to any right of termination, cancellation or acceleration under, any
of the terms or conditions of any note, bond, mortgage, indenture, license,
agreement or other instrument or obligation to which any of the Investors is a
party or by which any of them or any of their properties or assets may be bound,
or (iii) violate any statute or law, or any rule, regulation, writ, injunction,
judgment, order or decree of any court, administrative agency or governmental
authority binding on the Investors, or any of their respective properties or
assets, excluding from the foregoing clauses (ii) and (iii), conflicts,
violations, breaches and defaults which, individually and in the aggregate,
would not have a material adverse effect on the ability of the Investors to
perform their respective obligations hereunder.

         (c)      Title to Shares. The Company shall, upon delivery of the
shares of Common Stock held by the Investors as a result of (A) repurchase by
the Company of the amount of such shares pursuant to Section 1.2 hereto or (B)
repurchase by the Company of the amount of such shares pursuant to Section 1.3
hereto, obtain valid and marketable title to such Common Stock, free and clear
of any lien, claim, charge, equity or encumbrance of any kind.

         (d)      Consents and Approvals. No authorization, consent, order or
approval of or notice to or filing with, any federal, state, provincial or local
governmental authority is required in connection with the execution, delivery
and performance by the Investors of this Agreement or of the performance of
their respective obligations hereunder, except for those required under U.S.
federal securities laws, state "blue sky" laws and/or Canadian securities laws
in connection with the IPO and the Registration Rights Agreement.

<PAGE>

                                                                               9

                                   ARTICLE III

                                CERTAIN COVENANTS

         3.1      PERFORMANCE. Each of the parties hereto covenants and agrees
that it shall not avoid or seek to avoid the observance or performance of any of
the terms of this Agreement, but will at all times in good faith assist in the
carrying out of all such terms and in the taking of all such action as may be
reasonably necessary or appropriate to protect the rights of the parties hereto
against impairment of their respective rights hereunder.

         3.2      ISSUABLE SUBORDINATED NOTES. The Company shall at all times
have authorized and issuable under the indenture related to the Subordinated
Notes a sufficient aggregate principal amount of Subordinated Notes so that the
Company will be able to deliver the Subordinated Notes to the transferees of the
Investors in accordance with the terms of this Agreement.

                                   ARTICLE IV

                    CONDITIONS TO OBLIGATIONS OF THE PARTIES

         4.1      CONDITIONS TO OBLIGATIONS OF THE COMPANY. The obligation of
the Company to consummate the transactions contemplated hereby shall be subject
to the satisfaction or waiver of the following conditions on or prior to each of
(i) the date of repurchase by the Company of the shares of Common Stock upon
completion of the IPO pursuant to Section 1.2 hereto, (ii) the date of
repurchase by the Company of the shares of Common Stock upon exercise of the
Over-allotment Option pursuant to Section 1.3 hereto and (iii) any transfer and
exchange date pursuant to Section 1.4(a) hereto (each such date a "Performance
Date"), as applicable:

         (a)      Representations, Warranties and Covenants of the Investors.
The representations and warranties of the applicable Investors contained in this
Agreement shall be true and correct in all material respects when made and at
and as of the applicable Performance Date as if made at and as of such date, and
each of the applicable Investors shall have performed or complied in all
material respects with all agreements and covenants required by this Agreement
to be performed or complied with by it prior to or at and as of the applicable
Performance Date.

         (b)      Consents. All governmental and regulatory consents, approvals,
authorizations, declarations, filings and registrations necessary for
consummation of the transactions contemplated hereby shall have been obtained.

         (c)      No Governmental or Other Proceeding. There shall not exist any
statute, rule, regulation, executive or other order, judgment, injunction, stay
or decree that restrains or prohibits the Company from consummating the
transactions contemplated hereby, and there shall be no litigation or
administrative or regulatory proceeding pending or threatened which, in the
reasonable judgment of the Company, is likely to restrain, prohibit or result in
the imposition of

<PAGE>

                                                                              10

materially adverse conditions on the ability of the Company to consummate any of
such transactions.

         4.2      CONDITIONS TO OBLIGATIONS OF THE INVESTORS. The obligation of
the Investors to consummate the transactions contemplated hereby shall be
subject to the satisfaction or waiver of the following conditions on or prior to
each Performance Date, as applicable:

         (a)      Representations, Warranties and Covenants of the Company. The
representations and warranties of the Company contained in this Agreement shall
be true and correct in all material respects when made and at and as of the
applicable Performance Date, as if made at and as of such date, and the Company
shall have performed or complied in all material respects with all agreements
and covenants required by this Agreement to be performed or complied with by it
prior to or at and as of the applicable Performance Date.

         (b)      Consents. All governmental and regulatory consents, approvals,
authorizations, declarations, filings and registrations necessary for
consummation of the transactions contemplated hereby shall have been obtained.

         (c)      No Governmental or Other Proceeding. There shall not exist any
statute, rule, regulation, executive or other order, judgment, injunction, stay
or decree that restrains or prohibits the applicable Investor from consummating
the transactions contemplated hereby, and there shall be no litigation or
administrative or regulatory proceeding pending or threatened which, in the
reasonable judgment of the applicable Investor, is likely to restrain, prohibit
or result in the imposition of materially adverse conditions on the ability of
the such Investor to consummate any of such transactions.

         (d)      Registration Rights Agreement. On the consummation of the IPO,
the Company shall have executed and delivered the Registration Rights Agreement
and on the applicable Performance Date, the Registration Rights Agreement shall
be in full force and effect pursuant to its terms.

                                    ARTICLE V

                                  MISCELLANEOUS

         5.1      TERM. Unless otherwise agreed to in writing by the parties
hereto, the term of this Agreement shall commence on the date hereof and end on
the date, if any, on which the Company shall have advised the Investors that it
has abandoned its plans to consummate the IPO, and otherwise shall end when no
shares of Common Stock are subject to exchange pursuant to Section 1.4(a)
hereto.

         5.2      SUCCESSORS. All the provisions of this Agreement by or for the
benefit of the parties hereto shall bind and inure to the benefit of their
respective successors and assigns and the parties agree that any transferee by
distribution in kind of shares of Common Stock shall be deemed to be a successor
party to this agreement upon accepting such shares of Common Stock.

<PAGE>

                                                                              11

         5.3      NO ASSIGNMENT. The Company may not assign any of its rights or
delegate any of its duties under this Agreement without the prior written
consent of each Investor. Subject to applicable law and the following sentence,
the Investors may assign their rights under this Agreement in whole or in part
only in accordance with this Agreement and, if applicable, in accordance with
Section 7.8 of the Registration Rights Agreement. Each transferee, by accepting
the transfer of any Common Stock from an Investor or a subsequent transferee,
will be deemed to have agreed to be bound by this Agreement as an Investor (and
if the transferee agrees in writing to be bound by this Agreement, such Investor
shall be released from any obligations under this Agreement). Any purported
assignment in violation of this Agreement shall be void.

         5.4      HEADINGS. The headings of articles and sections of this
Agreement have been inserted for convenience of reference only, are not to be
considered a part hereof and shall in no way modify or restrict any of the terms
or provisions hereof.

         5.5      REMEDIES; AMENDMENT. The rights and remedies of the parties
hereto are cumulative and not exclusive of any rights or remedies which they
would otherwise have. This Agreement may be amended or modified only by a
written instrument signed by each of the parties hereto; provided however, that
if any Investor no longer owns any shares of Common Stock, such Investor shall
no longer be a party to this Agreement and shall not be required to sign such
written instrument.

         5.6      SEVERABILITY. Whenever possible, each provision of this
Agreement will be interpreted in such manner as to be effective and valid under
applicable law, but if any provision of this Agreement is held to be invalid,
illegal or unenforceable in any respect under any applicable law or rule in any
jurisdiction, such invalidity, illegality or unenforceability will not affect
any other provision, and such invalid, void or otherwise unenforceable
provisions shall be null and void. It is the intent of the parties, however,
that any invalid, void or otherwise unenforceable provisions be automatically
replaced by other provisions which are as similar as possible in terms to such
invalid, void or otherwise unenforceable provisions but are valid and
enforceable to the fullest extent permitted by law.

         5.7      GOVERNING LAW. This Agreement shall be governed by and
construed in accordance with the laws of the State of New York, except to the
extent that the laws of the State of Delaware are mandatorily applicable.

         5.8      NOTICES. Any notice, request, instruction or other document
(each, a "notice") to be given hereunder by any party hereto to any other party
hereto shall be in writing and shall be deemed to have been duly given if
delivered personally, sent by facsimile transmission, or registered or certified
mail, postage prepaid, to the parties hereto at the following addresses or to
such other addresses as any party hereto shall hereafter specify by notice to
the other party or parties hereto:

<PAGE>

                                                                              12

                  (a) If to the Company to:

                           Volume Services America Holdings, Inc.
                           300 First Stamford Place
                           Stamford, CT 06902
                           Attention: Janet Steinmayer

                  (b) If to the Blackstone Group to:

                           The Blackstone Group
                           345 Park Avenue
                           31st Floor
                           New York, NY 10154
                           Attention:  Howard Lipson

                  (c) If to the GE LLC to:

                           GE Capital Corporation
                           201 High Ridge Road
                           Stamford, CT 06927
                           Attention: Barbara Lane

         Any notice, request, instruction or document shall be deemed to have
been received on the date of delivery thereof.

         5.9      COUNTERPARTS; FACSIMILE SIGNATURE. This Agreement may be
executed in counterparts, each of which when so executed shall be deemed to be
an original, and such counterparts shall together constitute one and the same
instrument. This Agreement may be executed by facsimile signature.

         5.10     ENTIRE AGREEMENT. This Agreement and the Registration Rights
Agreement constitute the entire agreements and understandings of the parties
hereto in respect of the subject matter contained herein, and there are no
restrictions, promises, representations, warranties, covenants, or undertakings
with respect to the subject matter hereof, other than those expressly set forth
or referred to herein and in the Registration Rights Agreement. This Agreement
and the Registration Rights Agreement supersede all prior agreements and
understandings among the parties hereto with respect to the subject matter
hereof.

<PAGE>

                  IN WITNESS WHEREOF, the parties hereto have executed this
AMENDED AND RESTATED STOCKHOLDERS AGREEMENT as of the day and year first above
written.

                                    VOLUME SERVICES AMERICA HOLDINGS, INC.

                                    By:         /s/ Kenneth R. Frick
                                        ------------------------------------
                                        Name:  Kenneth R. Frick
                                        Title: Executive Vice President
                                               & Chief Financial Officer

                                    BCP VOLUME L.P.

                                    By: Blackstone Capital Partners II
                                        Merchant Banking Fund L.P.

                                        By: Blackstone Management Associates II
                                            L.L.C., as General Partner

                                            By:      /s/ Howard A. Lipson
                                                -------------------------------
                                                Name:  Howard A. Lipson
                                                Title: Attorney-in-fact

                                    BCP OFFSHORE VOLUME L.P.

                                    By:  Blackstone Offshore Capital Partners
                                         II L.P.

                                         By: Blackstone Management Associates
                                             II L.L.C., as General Partner

                                             By:     /s/ Howard A. Lipson
                                                 ------------------------------
                                                 Name:  Howard A. Lipson
                                                 Title: Attorney-in-fact

                                         By: Blackstone Service (Cayman) LDC, as
                                             Administrative General Partner

                                             By:     /s/ Howard A. Lipson
                                                 ------------------------------
                                                 Name:  Howard A. Lipson
                                                 Title: Attorney-in-fact

<PAGE>

                                                                              14

                                    VSI MANAGEMENT DIRECT, L.P.

                                    By:  VSI Management I L.L.C., as General
                                         Partner

                                         By:          /s/ Kenneth R. Frick
                                             ----------------------------------
                                             Name:  Kenneth R. Frick
                                             Title: Managing Member

                                         By: Blackstone Management Associates II
                                             L.L.C., as Managing Member

                                             By: /s/ Howard A. Lipson
                                                 ------------------------------
                                                 Name:  Howard A. Lipson
                                                 Title: Attorney-in-fact

<PAGE>

                                     RECREATIONAL SERVICES L.L.C.

                                     By:  General Electric Capital Corporation,
                                          as Managing Member

                                          By:      /s/ James C. Ungari
                                              ----------------------------------
                                              Name:  James C. Ungari
                                              Title: Vice President