How can I start and bind to a service in Android?

I am trying to start a Service in Android:

Log.d("BLE", "Start Service");
Intent gattServiceIntent = new Intent(this, BluetoothLeService.class);
bindService(gattServiceIntent, mServiceConnection, BIND_AUTO_CREATE);
startService(gattServiceIntent);
Log.d("BLE", "Service Started");

In the BluetoothLeService I override the onStartCommand() function which means I would see the log when the service is started

public class BluetoothLeService extends Service {
   ....  
   @Override
   public int onStartCommand(Intent intent, int flags, int startId) {
      // Let it continue running until it is stopped.
      Toast.makeText(this, "Service Started", Toast.LENGTH_LONG).show();
      Log.d("BLE", "onStartCommand");
      return START_STICKY;
}

However the log is the following:

07-14 21:30:23.676: D/BLE(28327): Start Service
07-14 21:30:23.676: D/BLE(28327): Service Started

but the onStartCommand() never appeared in the log. How can I start the service?

What you're trying to do is to bind to the service first and then start it. Documentation says:

A bound service is one that allows application components to bind to it by calling bindService() in order to create a long-standing connection (and generally does not allow components to start it by calling startService()).

The lifecycle of a service created by calling bindService() has different callback methods compare to the one created by calling startService() (see the flow diagram on the page provided). So for the service created with a bindService() call there is no onStartCommand() method, that's why it's never called.

The common practice is to start a service first and after that bind to it (all the hook methods must be appropriately implemented in this case). If you do it this way onStartCommand() will be called.

EDIT:

How can I start the service?

You did start the service. After calling bindService() it is running (of course if onBind() is properly implemented with IBinder returned).

... but the onStartCommand newer appeared in the log

It is so due to the reason described above.