Windows Deployment Services depends and works directly with Active Directory and DHCP, meaning that if any of those two servers are significantly modified, then probably you will not be able to start the WDS service and get the events ID:

Event Viewer from WDS Server

Event 257: An error occurred trying to start the Windows Deployment Services server.

Event 258: An error occurred trying to start the Windows Deployment Services image server.

Event 266: An error occurred while to refreshing settings.

Event 513: An error occurred trying to initialize provider WDSImgSrv from C:\Windows\system32\WdsImgSrv.dll. Windows Deployment Services server will be shutdown.

Disclaimer
Please note that the following possible reasons, are related when all those events appear simultaneously and with the same descriptions.

Event ID 513 can also appear regarding to a PXE provider error: “An error occurred while trying to initialize provider WDSPXE from C:\Windows\system32\wdspxe.dll. Windows Deployment Services server will be shutdown”. This particular error could happen for several reasons, like installing on the same server a System Center Configuration Manager PXE provider that replaces the WDS.

Possible Reasons

Those particular errors appeared when there were changes on Active Directory that did not were performed smoothly:

– Changing a Global Catalog from Domain Controller.
– Shutting down an active Domain Controller.

Solution

To solve this, you need to insert manually the FQDN of the domain controller working as a Global Catalog.

1 – Open the WDS snap-in and access server properties.

2 – Click on “Advanced“.  And you should see the following:

3 – Insert the FQDN of a Domain Controller and the Global Catalog nearest to WDS and currently active (preferred in same site). Most likely will be the same DC on both options.

4 – Start the WDS Server.

More Background about WDS and Active Directory Integration

The PXE provider delivered with Windows Deployment Services is called BINL (implemented in Binlsvc.dll) and has a direct integration with Active Directory services in many ways:

• BINL prefers to use domain controllers and global catalogs that are available within the same Active Directory site as the PXE server (local).
• A writeable domain controller for the domain where the Windows Deployment Services PXE server resides will be leveraged when querying for selected attributes.
• The WDS PXE provider uses the DSGetDcName() API. It passes the DS_GC_SERVER_REQUIRED flag whenever it needs to locate a global catalog.
• When attempting to locate computer account objects, the default search order is for BINL to search global catalogs before searching domain controllers.
• And of course, BINL connects directly with AD when trying to create Computer objects within the domain; or querying for other attributes.

Example of BINL handling PXE requests and integrating with AD

For more info, check “Deploying and Managing the Windows Deployment Services Update”.

Hope it helps!

Cheers!